Well, at least SSH could allow for signing a new key with the old one. So they could say it's signed, and people would know to accept only a different prompt.

There is DNS verification, but people have been trained all their lives to accept insecure DNS information (and set their systems accordingly), and I really doubt the SSH client checks the DNSSEC data.