openssh client uses user given name to authenticate a server against the known_hosts file. the name can be letters or ip address.
In the former case, it's matched against Host entry in ssh_config and if the Host entry has HostName set it's used to check against known_hosts file. If the matched Host entry has no HostName set, the user supplied letters on the cli are checked against known_hosts file.
In the latter case, ip adress is checked. So a single host may have multiple entries each matching user supplied 'string of chars'. It happens because user can connect by ip, fqdn, a host entry in ssh_config file or just a dns prefix. When users refer to the same machine different way, the warning usually appears.
The above warning says the host is unknown. It means the client has'nt connected to this host before with this name or the client has connected to this host before with this name but the 'host key' of the host was not cached or cached and the cached key was removed meantime or cache has been corrupted or removed.
If you have connected to this host with example.com and cached the server host key earlier, the next time you connect to the host with example.com and if the server key is different from the cached one, the client would scream like remote host identification has changed, possible monkey-in-the-middle-attack.
openssh servers use four types of keys rsa, dsa, ecdsa and ed25519. It means the client must cache all the keys it's comfortable with.
Server keys fingerprint database must be built to cope with situation like this one. ssh-keygen -lf ssh_host_rsa_key.pub >> $HOME/example.com_host_key.txt
for each key.
HKEY_CURRENT_USER\SoftWare\SimonTatham\PuTTY\SshHostKey
?/var/log/messages
?/var/log/secure
?history
?