I am trying to connect to a server I have previously connected to. However newer version of OpenSSH does not use DSA keys. I get the following error when trying to connect:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!Someone could be eavesdropping on you right now (man-in-the-middle attack)!It is also possible that a host key has just been changed.The fingerprint for the ***RSA*** key sent by the remote host isSHA256:mxVLlJWwlY7pRm1nhOksy0eS4KIQbAE8nv7x0p3Ds8Q.Please contact your system administrator.Add correct host key in /Users/john/.ssh/known_hosts to get rid of this message.Offending ***DSA*** key in /Users/john/.ssh/known_hosts:25***RSA*** host key for example.com has changed and you have requested strict checking.Host key verification failed.I have figured out that the problem is that DSA key is stored in known_hosts but there is no RSA key yet. Adding the RSA key fixes the problem.I think the message is misleading, the RSA host key did not change.I would expect OpenSSH to inform me that there is no RSA key yet and offer me to add the key. It should also check DNS for the key and show Matching host key fingerprint found in DNS. message (which I have set up).Is it worth reporting to OpenSSH as a bug?
Why does SSH reports possible man-in-the-middle with different key types?
ssh;openssh
I think the message is misleading, the RSA host key did not change.The message is valid. The key in your known_hosts is DSA and the server sends RSA, they differ and it is wrong.Since OpenSSH 6.8 the server sends all the keys after authentication to simplify the hostkey rotation or deprecation.If you have new enough client and server, go on with workaround, temporary accept the DSA keys and let the client pick up the new ones:ssh -oHostKeyAlgorithms=+ssh-dss your_remote_hostif the server has older version, you need to do that manually as you explain in the question.This also needs a client configured to accept the new keys: UpdateHostKeys yes.