GPS depends on satellites to stay in the right place, intact, and powered, as well as the ability to receive authentic RF signals from those satellites.
Celestial navigation requires (the computational equivalent of) a graphing calculator.
Is there a reason why the signals aren't digitally signed? I understand that GPS and GLONASS was deployed over 30 years ago, but surely Galileo, with its first satellite launched 4 years ago can have this?
Spoofing of GPS signals isn't generally the problem the US military is most concerned about. It's availability.
The assumption is that in any significant event, US space assets will be unavailable either momentarily or for some extended period. Chinese Anti-SAT weapons are one indicator that this is a likely avenue of attack for any weaker actor seeking to degrade our capabilities.
So, celestial navigation is a crude but workable substitute for GPS but it has the distinct advantage of being ancient and nearly impossible to impede unless you can change the weather or the positions of the heavenly objects.
Celestial navigation requires (the computational equivalent of) a graphing calculator.