When connecting to an SSH server you control, you might encounter this security warning about changed host keys. While the standard solution is to remove the old key, there are valid reasons to maintain multiple keys for a single hostname.

The ~/.ssh/known_hosts file stores host keys in this format:

hostname,ip ssh-rsa AAAAB3NzaC1yc2EAAA...==
[hostname]:port ecdsa-sha2-nistp256 AAAAE2VjZ...=

To add a new key without removing the old one:

# First get the new fingerprint
ssh-keyscan -t rsa,ecdsa,ed25519 hostname >> ~/.ssh/known_hosts

# Then verify both entries exist
grep "hostname" ~/.ssh/known_hosts

For a more controlled approach:

# Remove just the problematic line (not the entire entry)
ssh-keygen -R "[hostname]:port" -f ~/.ssh/known_hosts

# Add new key with verification
ssh-keygen -F hostname || ssh-keyscan hostname >> ~/.ssh/known_hosts

When migrating between key types during server upgrades:

# Allow both old RSA and new ED25519 keys temporarily
{
  ssh-keyscan -t rsa hostname
  ssh-keyscan -t ed25519 hostname
} >> ~/.ssh/known_hosts

# Verify with
ssh -o HostKeyAlgorithms=ssh-rsa,ssh-ed25519 hostname

• Use ssh-keygen -l -f ~/.ssh/known_hosts to list all known fingerprints
• Consider using ~/.ssh/known_hosts2 for hashed hostnames
• For automation, use -o StrictHostKeyChecking=accept-new in SSH config

While maintaining multiple keys can be useful during transitions, always:

1. Verify new fingerprints through out-of-band channels
2. Remove deprecated keys after migration periods
3. Monitor for unexpected key changes

When you encounter the dreaded "WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED" message, it typically means one of two things:

1. A legitimate key rotation has occurred on the server
2. A potential man-in-the-middle attack is underway

The standard advice is to remove the old entry from ~/.ssh/known_hosts, but what if you need to maintain both keys?

The known_hosts file can indeed store multiple keys for the same hostname. The format supports this through hashed and unhashed entries:

hostname ssh-rsa AAAAB3NzaC1yc2EAAA... (old key)
hostname ssh-rsa AAAAB3NzaC1yc2EAAA... (new key)

Here's how to add a new key while preserving the old one:

ssh-keyscan -t rsa yourhostname >> ~/.ssh/known_hosts

Or for a more precise approach:

ssh-keygen -R yourhostname
ssh-keyscan -H yourhostname >> ~/.ssh/known_hosts

For automation scenarios, you might want to handle this in a script:

#!/bin/bash
HOST="example.com"
PORT=22

# Remove all existing entries
ssh-keygen -R "$HOST" -f ~/.ssh/known_hosts
ssh-keygen -R "[$HOST]:$PORT" -f ~/.ssh/known_hosts

# Add new keys for all supported algorithms
for type in rsa dsa ecdsa ed25519; do
    ssh-keyscan -t "$type" -p "$PORT" "$HOST" >> ~/.ssh/known_hosts
    ssh-keyscan -t "$type" -p "$PORT" "[$HOST]:$PORT" >> ~/.ssh/known_hosts
done

While maintaining multiple keys can be useful during transitions, consider:

• This approach slightly reduces security during the transition period
• Best practice is to minimize the overlap window
• Consider using SSH certificates instead of raw keys for better manageability

You can configure your SSH client to accept specific key types:

Host example.com
    HostKeyAlgorithms ssh-rsa,ssh-dss