When you encounter the "WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!" message during an SSH connection, it indicates that the SSH client has detected a discrepancy between the server's current host key and the key previously recorded in your known_hosts file. This could be due to a legitimate server change, but it also could indicate a potential security threat, such as a man-in-the-middle attack.

To resolve this issue, you should verify the change and update your known_hosts file if the change is legitimate.
Lets see how  to do so safely:

1. Verify the Host Key Change
Contact the server administrator or use an out-of-band method to verify that the host key change is legitimate.
Obtain the new host key fingerprint from a reliable source.

2. Remove the Old Host Key from known_hosts
To remove the old host key entry, follow these steps:

Option 1: Using ssh-keygen Command

ssh-keygen -R hostname_or_ip

Replace hostname_or_ip with the actual hostname or IP address of the server.
For Example:
ssh-keygen -R linuxfaq.com

This command removes all keys associated with linuxfaq.com from the known_hosts file.

Option 2: Manually Editing the known_hosts File
Open the known_hosts file in a text editor:
nano ~/.ssh/known_hosts


Find and Remove the Old Entry:
Search for the line that contains the hostname or IP address of the server. Remove that line.

Save and Close:
Save the file and exit the editor.

3. Reconnect to the server:
Once the old key is removed, reconnect to the server to add the new host key:
ssh username@hostname_or_ip

For Example:
ssh user@linuxfaq.com

You will see a message similar to this:
The authenticity of host 'example.com (192.0.2.1)' can't be established.

ECDSA key fingerprint is SHA256:abc123def456...

Are you sure you want to continue connecting (yes/no/[fingerprint])?


Verify the fingerprint.
Type yes to add the new host key.

Handling Multiple Entries
If the server has multiple entries (e.g., different IP addresses), you might need to remove each entry:
ssh-keygen -R example.com

ssh-keygen -R linuxfaq.com


Summary
Verify: Confirm the host key change with the server administrator.
Remove: Use ssh-keygen -R hostname_or_ip or manually edit ~/.ssh/known_hosts to remove the old key.
Reconnect: SSH into the server to add the new host key after verification.

Following these steps ensures the security of your SSH connections and correctly handles the host key change.