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.
