TL;DR: SSH: “WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!” and “Host key verification failed”

The fix only. No explanation, no diagnosis. Read the full article if any of this does not match what you are seeing.

1. Make sure the change is expected: was the server rebuilt, reinstalled, restored from an image, or did the IP address move to another machine?

If you cannot explain the change, stop. Do not continue until you have asked whoever runs the server.

2. Note the fingerprint ssh printed ("The fingerprint for the ED25519 key sent by the remote host is SHA256:…"). On the server's console, check it matches:

ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub

3. Remove only the stale entry. For a server on a non-standard port, use the bracket form. Use exactly the name you type after ssh.

ssh-keygen -R server1.example.com
ssh-keygen -R "[192.168.1.50]:2222"

4. Connect again, check the fingerprint in the prompt matches step 2, and answer yes.
5. Verify the new entry is saved:

ssh-keygen -F server1.example.com

Do not delete the whole known_hosts file, and do not turn off StrictHostKeyChecking. That removes the protection for every server, not just this one.

← Full article, with the diagnosis and the why