You're right, it won't shuffle back.
I can see why one would think it does; when a creature dies, auras on it die as well. God-Eternal Oketra will enter the graveyard unenchanted, so it 'seems to have' its third ability again, and it should trigger, right? No:
112.6. ... Abilities of all other objects usually function only while that object is on the battlefield. ...
There follows a list of exceptions, e.g. "An object’s ability that modifies how that particular object enters the battlefield functions as that object is entering the battlefield.", but leaving the battlefield (by dying or by being exiled) is not one of them.
So the third ability functions only on the battlefield (or more precisely, it's a special case of 603.10a; the game looks backs to the state on the battlefield), and while it's on the battlefield, it's still enchanted and loses all abilities due to Deep Freeze.