I'm trying to connect to a server that I previously connected to. The last
time I connected to it, ssh used its ECDSA key for host verification. This is
the only key in my known hosts file:

    $ cat ~/.ssh/known_hosts | awk '{print $2}' | uniq
    ecdsa-sha2-nistp256

The server is no longer offering this key. This is what I get when I try to
connect now:

    $ ssh user@host -p 23
    @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
    @    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 is
    SHA256:VzEhMh3aw2lqAsZSdLbYJAhwW4yIgUxCRotrMoWqzT9.
    Please contact your system administrator.
    Add correct host key in /home/user/.ssh/known_hosts to get rid of this message.
    Offending ECDSA key in /home/user/.ssh/known_hosts:1
      remove with:
      ssh-keygen -f "/home/user/.ssh/known_hosts" -R "[host]:23"
    RSA host key for [host]:23 has changed and you have requested strict checking.
    Host key verification failed.

I am expecting to get this warning, but the penultimate line sounds wrong to
me. From the point of view of ssh, "RSA host key" shouldn't appear changed; it
didn't know anything about it at all. In fact, the actual RSA key on the 
server never changed. What changed was the type of key offered by the server.

I think the error message should reflect that.

To reproduce, run

    /usr/sbin/sshd -ddd -p 23 -oHostKeyAlgorithms=ecdsa-sha2-nistp256

Connect to let ssh remember the key, then run

    /usr/sbin/sshd -ddd -p 23 -oHostKeyAlgorithms=rsa-sha2-256

Connect again and observe the error