Engines at the size and performance of an SSME are very difficult to develop.
The SSME has one of the highest ISP's ever attained in a production engine. (Not some crazy Fluorine involving demo). It is anything but a simple, or even 'old' engine. Its re-manufacture would likely benefit from modern techniques, like the people examining starting F-1 engine rebuilds.
It has been estimated (I have no source, only what is usually quoted) to take 6-10 years to develop a large engine.
The SSME is not that high in thrust, compared to the F-1 (660 Klbs SSME vs 1.5-1.8 MLbs thrust) but is much higher than something like a Merlin 1D (165 Klbs thrust).
The closest comparable (LOX/LH2) engine is the RS-68 used by the Delta 4 booster but was rejected because the heat load under the first stage, surrounded by the SRBs was unsurvivable by the RS-68. (Whereas the SSME was always designed to be 'near' the SRBs during launch. I say 'near' since of course, on the Shuttle they were offset being on the back of the orbiter, not directly between as they would be on SLS)
Is it rational to restart SSME production? Maybe. It is a well understood, mature engine, that might benefit from moderm manufacturing technologies. It is a very advanced engine with excellent performance. It has been pointed out in the comments that some of the newest engines of that remaining set of 16 were manufactured as late as 2008.
I have this graphic of which SSME was used on which STS flight.
How expensive would a new engine be? Very. It would require performance similar to the SSME, else the size of tanks or # of engines would cascade rippling changes throughout the entire SLS stack probably killing it.
The SSME was quite expensive and something comparable to it would be similarly hard to develop.
Any ready replacements? Nothing really. The RS-68 is the closest and already rejected. Would a Russian engine be accepted? Not sure there is an appropriatly sized LOX/LH2 Russian engine on the shelf. The Russians have been great at BIG Kerosene engines. (RD-170, RD-180, RD-193) But LH2 mechanics at the large scale have usually caused them issues.
The Ariane 5 Vulcain main engine might be an interesting idea, as it currently runs beneath the A5 main stage with an SRB on either side of it, but I would guess the sizing is wrong.
Having said all that, it seems like more reason to consider SLS less of a great option.