I am quite certain a paraphrase of the quote "the only place where medieval theology survives is pure math", attributed to one of Gödel's essays by Chaitin, does not appear in his collected works (see Vol III: Unpublished essays and lectures). (At least a search for "medieval" and "theology" only returns references to Gödel's ontological proof for the existence of God.)
However, if I understand the question in the OP more generally as an interest in this line of thought of Gödel, then the 1961 essay The modern development of the foundations of mathematics in the light of philosophy develops it as follows:
I would like to attempt here to describe, in terms of philosophical concepts, the development of foundational research in mathematics since around the turn of the century, and to fit it into a general schema of possible philosophical world-views. For this, it is necessary first of all to become clear about the schema itself. I believe that the most fruitful principle for gaining an overall view of the possible world-views will be to divide them up according to the degree and the manner of their affinity to or, respectively, turning away from metaphysics (or religion). In this way we immediately obtain a division into two groups: skepticism, materialism and positivism stand on one side, spiritualism, idealism and theology on the other.
[...]
Now it is a familiar fact, even a platitude, that the development of philosophy since the Renaissance has by and large gone from right to left - not in a straight line, but with reverses, yet still, on the whole. Particularly in physics, this development has reached a peak in our own time. [...] It would truly be a miracle if this (I would like to say rabid) development had not also begun to make itself felt in the conception of mathematics. Actually, mathematics, by its nature as an a priori science, always has, in and of itself, an inclination toward the right, and, for this reason, has long withstood the spirit of the time that has ruled since the Renaissance.
In connection with the topic of Gregory Chaitin's interview, the question whether mathematics is invented or discovered: Gödel was inclined to the latter, and in a 1951 essay Some basic theorems on the foundations of mathematics and their implications cited Hermite: There exists, unless I am mistaken, an entire world consisting of the totality of mathematical truths, which is accessible to us only through our intelligence, just as there exists the world of physical realities; each one is independent of us, both of them divinely created.