Could pulsar navigation replace GPS as a follow-up to my previous question I found out that the Voyager Golden record uses a star map of pulsars to precisely show where our solar system is...

Is it possible/feasible to base a navigation system on pulsars in order to replace GPS?
Pulsar, or X-ray navigation is being actively tested right now. Currently an X-ray telescope mounted on the International Space Station completed a test where a small navigation computer was able to solve for it's own position and orbit in space relying only timing information from X-rays produced by a group of pulsars.
I've written more about it in the question Is NICER/SEXTANT the first civilian “spacecraft” to determine it's own position in space without GPS or uplinked data? Spoiler alert, hold your cursor over the box:

 Yes, it is the first

You can also read about an investigation for X-ray communication in How will NavCube (actually) be important for the XCOM testing and demonstration? I believe this will be a significantly longer term technology development path.
NICER, NASA’s Neutron star Interior Composition Explorer, will of course also be used for pure Astronomy research on neutron stars.
Will this replace GPS? Not really, No.
GPS serves the Earth's surface, and near Earth orbit (NEO) very nicely and efficiently. However, once you get a little farther, to MEO and GEO, it gets much more difficult to receive several simultaneous GPS signals because the satellites concentrate most of their power directly on to the Earth's disk, with only some side-lobes &quot;leaking&quot; past the terminator and into space.
See the questions and of course their answers:

Will Glonass, Galileo, or BeiDou-2 satellites provide better cis-lunar navigation than GPS?
Has GPS been used beyond GEO? (duplicate)
How far up have satellites used a GNSS for positioning, and how does the precision degrade with altitude?

So for spacecraft in farther Earth's orbits it may be possible to augment or replace GPS or GNSS in general, and for deep space, there is currently no way to autonomously navigate today, so it will be the first.


above: NICER X-ray timing telescope/concentrator array, from About NICER.