Please excuse the long story, I'm not sure how much of it is relevant.
Computers "S" and "C" are on a LAN - they have nonroutable ipv4 addresses on the same segment and are firewalled off from any incoming connection attempts.
'S' gets Ubuntu 16.04.x LTS Server installed, headless, and openssh-server, and static IP. Everything else on 'S' still has default settings.
On 'C' with OpenSSH client:
$ ssh email@example.com
And I accept the offered host key and everything works as expected. While on the shell to S I run apt-get update and ugprade.
Now I configure the client on C with lenient settings, to use either key or password authentication. And I generate keys on C, ed25519 and RSA.
Then login to S again, the welcome message says it needs a restart. Postponing that I move all the default server keys to a backup directory and generate new ones (to have control of keygen settings and make sure only strong ones are present). This works as expected and shows an ASCII pictogram for each key.
Now restart S, killing the session from C. Then login to S again, now of course its host keys are changed, and thanks to my cautious config there's a scary message and I have to delete the old host key from ~/.ssh/known_hosts. So I do that and start to login again.
The ASCII art and fingerprint are different, as expected. However they don't agree with the ones that were displayed when I was generating the keys.
I go ahead and login because I trust the situation (firewalled etc.). Now on S, the output of
$ ssh-keygen -lv -f ssh_host_ed25519_key.pub
is still the same as it was when I generated the keys:
256 SHA256:<longStringTheFirstHere> root@S (ED25519) +--[ED25519 256]--+ <ASCII art follows>
However at the same time I can login again from another shell and the host key presented is :
256 SHA256:<longStringTheSecondHere> root@S (ED25519) +--[ED25519 256]--+ <different ASCII art>
So I'm trying to understand why there is this difference. Has something gone wrong? Is there a security problem? More likely something I'm missing but I'd like to know what it is.
I've found many pages on related topics but not quite this issue.