— Kiaasa Dhanori Pune

To regenerate SSH host keys on a Linux server, delete the old key files in /etc/ssh and run ssh-keygen -A to recreate every modern key type automatically, then restart the SSH service. Regenerating SSH host keys is a routine but critical task whenever you clone a server image, suspect a key compromise, or need to fix the dreaded WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED message. This guide walks through the correct modern commands, explains why the legacy advice you may have seen is dangerously outdated, and shows how to clean the client-side cache so connections work again.

What SSH host keys are and why you regenerate them

Every OpenSSH server has a set of host keys stored in /etc/ssh. These keys are how a server proves its identity to clients. The first time you connect, your SSH client records the server's public key fingerprint. On every later connection it compares the presented key against that saved record. If they match, you are talking to the same machine. If they do not, SSH warns you loudly, because a mismatch can mean a man-in-the-middle attack.

You need to regenerate SSH host keys in several common situations:

• You deployed a server from a cloned image or template and several machines now share identical host keys (a real security problem).
• The private host keys may have been exposed or compromised.
• You are migrating to stronger, modern key algorithms and want to retire weak ones.
• A package or configuration error left the keys missing or corrupted, blocking the sshd service from starting.

Host keys are not the same as user keys. User keys (the ones in ~/.ssh/id_ed25519) authenticate you to the server. Host keys authenticate the server to you. This guide is strictly about the server-side host keys.

The modern, correct way to regenerate SSH host keys

On any current OpenSSH release the simplest and safest approach is a single command. The -A flag tells ssh-keygen to create host keys for all default key types that do not already exist, each in its standard path with the correct filename, and with no passphrase (host keys must be passphrase-free so sshd can read them at boot).

1. Open a root shell or prefix commands with sudo.
2. Remove the existing host keys so they are recreated fresh:
   sudo rm -v /etc/ssh/ssh_host_*
3. Regenerate every default key type automatically:
   sudo ssh-keygen -A
4. Restart the SSH daemon so it loads the new keys:
   sudo systemctl restart ssh (Debian/Ubuntu) or sudo systemctl restart sshd (RHEL/Fedora/SUSE).

That is the whole job on a modern system. ssh-keygen -A produces an Ed25519 key and an RSA key (and, depending on the build, ECDSA). These are the algorithm types OpenSSH supports and recommends today.

Generating individual keys by hand

If you prefer explicit control, generate each key type yourself. Make sure every file path is different and that -N '' (two single quotes) sets an empty passphrase:

1. Ed25519 (recommended default — fast, compact, very strong):
   sudo ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ''
2. RSA (use 4096 bits; keep it for compatibility with older clients):
   sudo ssh-keygen -t rsa -b 4096 -f /etc/ssh/ssh_host_rsa_key -N ''
3. ECDSA (optional; only if your environment specifically requires it):
   sudo ssh-keygen -t ecdsa -b 521 -f /etc/ssh/ssh_host_ecdsa_key -N ''

Each command writes two files: the private key (e.g. ssh_host_ed25519_key) and its public counterpart (ssh_host_ed25519_key.pub). After creating the keys, restart sshd as shown above.

A critical warning about the legacy SSH1, RSA1, and DSA advice

Older tutorials — and some still-circulating documentation — instruct you to create three keys: an RSA1 key for the SSH1 protocol plus RSA and DSA keys for SSH2. Do not follow that advice on any current system. It is obsolete and, in the case of SSH-1, actively insecure.

• SSH protocol 1 (SSH-1) is broken and removed. It contains design flaws that allow practical attacks. OpenSSH disabled SSH-1 by default years ago and deleted all SSH-1 support entirely in OpenSSH 7.6 (2017). The rsa1 key type and the command ssh-keygen -t rsa1 no longer exist — running it on a modern build simply fails.
• DSA host keys are deprecated and disabled. DSA (the ssh-dss algorithm) is limited to 1024-bit keys and is considered weak. OpenSSH disabled DSA by default in OpenSSH 7.0 and removed it completely in OpenSSH 9.8 (2024). There is no reason to generate a DSA host key today.

So the original "three commands" recipe collapses into the modern reality: generate Ed25519 and RSA, skip RSA1 and DSA entirely. If you are administering a genuinely ancient system that still requires the legacy types, the right fix is to upgrade the OS, not to keep weak cryptography alive.

"The authenticity of host can't be established" — what it means

After you regenerate the host keys, the very next time you connect from a client you will see a prompt like this:

The authenticity of host 'server.example.com (203.0.113.10)' can't be established.
ED25519 key fingerprint is SHA256:abc123...
Are you sure you want to continue connecting (yes/no/[fingerprint])?

This is expected. The server's identity legitimately changed because you replaced its keys, and your client has no saved record of the new fingerprint. Modern OpenSSH prints a SHA256 fingerprint by default. (You may still see the old colon-separated MD5 style — 16:27:ac:a5:... — only when a client is configured with -o FingerprintHash=md5; SHA256 is the current standard.)

Where the client stores those fingerprints depends on the platform:

To verify you are accepting the right key, confirm the fingerprint the client shows matches one computed on the server itself before you type yes.

Removing the offending key from known_hosts

If a client previously connected to this server, the saved fingerprint no longer matches and you will get a much sterner message instead of a friendly prompt:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
...
Offending ECDSA key in /home/user/.ssh/known_hosts:15

Here /home/user/.ssh/known_hosts is the file and 15 is the exact line number of the stale entry. You have two clean ways to remove it.

Option 1 — the dedicated, safe command (recommended)

OpenSSH ships a flag built exactly for this. It removes every cached key for that host without touching anything else:

1. ssh-keygen -R server.example.com (use the hostname you connect with)
2. If you also connect by IP, remove that too: ssh-keygen -R 203.0.113.10

This automatically backs up the original file to known_hosts.old, so it is safer than hand-editing.

Option 2 — delete the specific line manually

Because the warning gives you the line number, you can jump straight to it. The original instinct to open vi at that line still works:

1. Open the file at the offending line: vi +15 ~/.ssh/known_hosts (note the order — the +15 comes before the filename).
2. Delete the whole line with dd, then save and quit with :wq.

Or do it non-interactively with sed (back up first): cp ~/.ssh/known_hosts ~/.ssh/known_hosts.bak && sed -i '15d' ~/.ssh/known_hosts. For PuTTY on Windows, open regedit, navigate to the SshHostKeys path above, and delete the value whose name contains the server's host and port.

Common pitfalls when you regenerate SSH host keys

• Forgetting the empty passphrase. Host keys must have no passphrase. If you omit -N '' in an interactive run and set one, sshd cannot read the key at boot and the service fails to start.
• Reusing the same filename. Each key type needs its own distinct path. Overwriting one file with another type leaves sshd with a broken configuration.
• Wrong file permissions. Private host keys must be 0600 and owned by root. If you copied keys around, fix them: sudo chmod 600 /etc/ssh/ssh_host_*_key and sudo chmod 644 /etc/ssh/ssh_host_*_key.pub.
• Not restarting sshd. The daemon loads host keys at startup. New keys do not take effect until you restart the service.
• Locking yourself out. Always keep your current session open and test a second login before closing it, so a misconfiguration does not strand you.
• Production keys in a different path. On some builds (notably FreeBSD or source installs) host keys live under /usr/local/etc/ssh rather than /etc/ssh. Check sshd_config for the HostKey directives if the standard path is empty.

Verification — confirm the new keys are live

After regenerating, verify everything works before you walk away:

1. Confirm the daemon is running cleanly: sudo systemctl status ssh (or sshd).
2. Print the new fingerprints so you have them on record: for f in /etc/ssh/ssh_host_*_key.pub; do ssh-keygen -lf "$f"; done
3. From a client (or a new terminal), connect and check the presented fingerprint matches the server output above, then accept it.
4. Validate the running config has no errors: sudo sshd -t — it prints nothing if the configuration is valid.

If the status is active (running), sshd -t is silent, and the client connects with a fingerprint that matches the server, the regeneration is complete and correct.

Key Takeaways

• The fastest correct method is sudo rm /etc/ssh/ssh_host_* then sudo ssh-keygen -A, followed by a service restart.
• Generate Ed25519 and RSA-4096 only — RSA1/SSH-1 and DSA are removed from modern OpenSSH and must never be used.
• Host keys carry no passphrase (-N '') and live in /etc/ssh (sometimes /usr/local/etc/ssh), each in its own file.
• The "identification has changed" warning is normal after regeneration — clear the stale client entry with ssh-keygen -R hostname.
• Always test a second login and run sshd -t before ending your session to avoid being locked out.

Frequently Asked Questions

Does regenerating SSH host keys disconnect active sessions?

No. Existing SSH sessions stay connected because the session key was already negotiated. New host keys only affect future connections, which is exactly why you should test a fresh login before closing your current one.

How do I regenerate host keys on Ubuntu or Debian specifically?

Run sudo rm /etc/ssh/ssh_host_* followed by sudo dpkg-reconfigure openssh-server, which calls ssh-keygen -A for you, or just run sudo ssh-keygen -A directly. Then sudo systemctl restart ssh.

Should I still create a DSA host key?

No. DSA is weak (capped at 1024 bits), was disabled by default in OpenSSH 7.0, and was removed entirely in OpenSSH 9.8 (2024). Use Ed25519 as your primary key and RSA-4096 for backward compatibility.

What is the difference between host keys and user keys?

Host keys in /etc/ssh prove the server's identity to clients. User keys in ~/.ssh prove your identity to the server. Regenerating host keys does not affect user logins, but clients will need to accept the new server fingerprint.

For more practical Linux, server, and DevOps walkthroughs, subscribe to @explorenystream on YouTube.