This is entirely the fault of the software. For planned key rotations, you could sign the new key with the old key and send that in the handshake, so the clien

This is entirely the fault of the software. For planned key rotations, you could sign the new key with the old key and send that in the handshake, so the client could change the known_hosts file on its own. For unplanned rotations (server got nuked), you could isntruct your users to use a secure connection and run "ssh-replace-key server.example.com b3f620", which would re-run TOFU, with the last param being an optional truncated hash of the key for extra security. You could also do a prompt like "DANGER!! The host key has changed. If you know this is expected or of your IT administrator told you to do so, type 'I know what I'm doing or the IT admin told me to do this' ".