Celestial navigation, under the best of circumstances, has nowhere near the accuracy of other systems. However, it is an emergency fall back provided reasonably clear skies and horizon. Understanding celestial sight reduction and using a sextant and clock is not trivial for the average person and requires practice to be proficient.
If electronic systems are removed, visual references, bearings, and accurate charts become much more important, just as they were in the days before GPS. Before GPS, I navigated to and through the northern Bahamas for 4 weeks using compass, handheld RDF, hand-drawn chartlets in the Yachtsman's Guide to the Bahamas, 2 small scale charts of the Gulf Stream and northern Bahamas, and my seaman's eye (for depths and visual references).
A guess on my part, but all the services probably occasionally practice navigation without electronics, just like you practice other emergencies.
Fred W