ssh-ed25519 and ecdsa-sha2-nistp256 host keys

[Ryan Mulligan]

Hello.

I am running OpenSSH 7.9p1 on my client and server. ssh-keyscan shows
the server has ssh-rsa, ssh-ed25519, and ecdsa-sha2-nistp256 host
keys. My /etc/ssh/ssh_known_hosts file contains the server's
ssh-ed25519 host key. When I try to SSH to the server I get this
error:


@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 ECDSA key sent by the remote host is
SHA256:{redacted}.
Please contact your system administrator.
Add correct host key in /home/ryantm/.ssh/known_hosts to get rid of
this message.
Offending ED25519 key in /etc/ssh/ssh_known_hosts:64
ECDSA host key for HOST has changed and you have requested strict checking.
Host key verification failed.


If I add `HostKeyAlgorithms -ecdsa-sha2-nistp256` to my SSH config
file it connects fine. If I order ssh-ed25519 before ecdsa in the
HostKeyAlgorithms it works fine (however, it then breaks if I only
have the ecdsa key in the known_hosts file.).

It seems like there is some equivalence of ssh-ed25519 and
ecdsa-sha2-nistp256 host keys.

I was expecting OpenSSH to look through all the host keys to find one
that matched my known_hosts entry. Is that an invalid expectation?

Do I need to add every host key to the known_hosts file to reliably connect?

Am I missing some configuration option that will make OpenSSH treat
these host keys distinctly?

Sincerely,
Ryan Mulligan