SSH Key Rotation Across a VPS Fleet: Inventory, Overlap, and Stale-Key Detection

Key rotation is easy on one server and painful on fifty. The failure modes are predictable: a key removed from two hosts but not the third, an automation account nobody remembers owning, and an authorized_keys file that grew organically for three years. This guide describes a repeatable process for auditing and rotating SSH keys across a VPS fleet without locking yourself out.

Build an inventory before you touch anything

You cannot rotate what you have not enumerated. Collect every authorized_keys file across the fleet, along with the comment field and fingerprint of each entry. A short loop over your host list produces a machine-readable snapshot you can diff later.

for host in $(cat hosts.txt); do
  ssh "$host" 'cat /root/.ssh/authorized_keys \
    /home/*/.ssh/authorized_keys 2>/dev/null' \
    | sed "s|^|$host |"
done > keys-inventory.txt

Then normalize: extract the key type, base64 blob, and comment for every line, and compute the SHA256 fingerprint with ssh-keygen -lf. Grouping by fingerprint immediately reveals which keys appear on the most hosts and which comments are missing. Keys with no comment are the ones that cause incidents.

Classify keys by purpose

Class	Examples	Rotation cadence
Human operator	Named engineer laptop keys	90 days or on offboarding
Automation	CI runners, deploy bots	180 days, scoped per host
Shared/service	Legacy shared logins	Eliminate; replace with roles
Break-glass	Emergency console key	Annual, stored offline

Shared accounts are the highest-risk category. They make attribution impossible and force you to rotate everywhere at once when any one holder leaves. Replace them with role-based certificates where possible. If you are still weighing how much operational overhead to carry in-house versus paying a provider, our managed vs unmanaged breakdown is a useful input.

Rotate without an outage

1. Generate the new keypair on the owner’s machine. Never generate private keys on a shared server.
2. Add the new public key to every host where the old one exists. Overlap matters: both keys work during the window.
3. Verify login with the new key on each host, including any hosts behind a bastion.
4. Remove the old public key only after verification passes everywhere.
5. Re-run the inventory and confirm the old fingerprint count is zero.

The overlap window is the critical control. Removing first and adding later is how teams lock themselves out of production at 02:00. Always add, verify, then remove.

Detect stale and orphaned keys

A key is stale when no session has used it in a defined period. Match your inventory against authentication logs to find candidates. The sshd logs record the key fingerprint for each accepted login when LogLevel VERBOSE is set, giving you a usage timestamp per key.

journalctl -u ssh --since "90 days ago" \
  | grep -i "Accepted publickey" \
  | grep -oE "SHA256:[A-Za-z0-9+/]+" \
  | sort | uniq -c | sort -n

Keys that never appear in this list but exist in the inventory are unused. Review them with the owner, then remove. Orphaned automation keys with no matching CI job should go immediately.

Automate enforcement

• Manage authorized_keys through configuration management, not by hand. The file becomes generated output, not editable state.
• Run the inventory weekly and alert on any fingerprint that appears on more hosts than expected.
• Block keys older than your policy with a scheduled report before they cause a scramble.
• Record every rotation in a changelog so audits have a paper trail.

If you are provisioning new instances, include the key-management baseline in your build image so no host ever starts life accepting direct human keys. Get the instance sizing and network assumptions right from the start by reading our VPS comparison, which covers the resource profiles typical for fleet management tooling.

Verification checklist

• Inventory exists and is regenerated automatically.
• Every key has an owner and a comment field.
• No shared login keys remain.
• Rotation ran add-verify-remove with an overlap window.
• Break-glass access is stored offline and tested.
• Session logs are centralized and retained long enough to answer audit questions.

Run this rotation on a schedule rather than after an incident. Teams that practice it quarterly find the process takes under an hour, while teams that defer it spend a weekend firefighting access problems under pressure.