SSH deploy hangs on host key verification after server rebuild

2026-11-13 · 3 min read

A deploy job sat at "Waiting for SSH…" for 18 minutes last month, then failed with Host key verification failed. Nothing had changed in the repo. What had changed was the box: the host was rebuilt from a new image at 02:10, and the pipeline's known_hosts still held the old Ed25519 key. Every subsequent run failed in the same place, and because the job ran under set -e inside a retry loop, it burned 40 minutes of CI time per attempt until someone noticed.

That's the cost. Below is what causes it and how to clear it without weakening host key checking more than necessary.

What the failure actually means

Host key verification failed is emitted by the client, not the server. OpenSSH stores the public host key of every server it connects to in ~/.ssh/known_hosts. On connect, the server presents its key; if it doesn't match what's stored, the client aborts before authentication. [link needed]

A rebuild regenerates /etc/ssh/ssh_host_*_key on first boot, so the presented key changes by design. The client is doing exactly what it should — it just has stale data. An SSH host key verification failed deploy is a caching problem, not a broken host.

Why an SSH host key verification failed deploy appears only after a rebuild

Three common triggers:

A *correct* host key change and a machine-in-the-middle look identical to the client. The fix below assumes you've confirmed the new key out of band.

Clearing it, in order

1. Confirm the new key is genuine. Read the fingerprint from the provider console or serial console: ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub. Compare against what the host serves. If they differ, stop and investigate.

2. Fetch the key you're about to trust: ssh-keyscan -t ed25519,rsa -H host.example.com > /tmp/newkeys.

3. Remove the stale entry. ssh-keygen -R host.example.com — this handles hashed entries too. Do it for every name and IP the pipeline uses.

4. Append the new key to the right file. For CI that's usually a dedicated file: cat /tmp/newkeys >> "$DEPLOY_KNOWN_HOSTS". Verify with ssh-keygen -F host.example.com -f "$DEPLOY_KNOWN_HOSTS".

5. Re-run the deploy. If it still hangs, look for a second known_hosts sourced by a different UserKnownHostsFile in the job's SSH config, and confirm the pipeline isn't connecting by IP while you fixed the hostname.

On the pipeline side, StrictHostKeyChecking=accept-new trusts an unseen key but still *rejects a changed one* — useful for first contact, not for the rebuild case. [link needed]

When not to do this

Don't reach for StrictHostKeyChecking=no plus UserKnownHostsFile=/dev/null on production hosts. It silences the error permanently, which means a swapped key never surfaces. Equally, don't paste in a new key blindly: if the host was rebuilt from an image that shipped shared, image-baked host keys, every instance of that image presents the same key, and you want to know that. [link needed]

Skip the manual steps entirely if your platform manages host keys centrally — regenerate through that path rather than editing files by hand.

Checklist