SSH warns the user, if the public key of a host is different from the one in known_hosts. Even long time SSH users don't know, that they can remove a key from the known_hosts file with ssh-keygen -R. They rather use self-made scripts to delete the line number indicated in the warning message. Please add information about ssh-keygen -R in the warning message.