Technically, changing your passphrase is sufficient if you don't also believe that your (password-protected) private key has also been leaked.
Realistically, you might just want to replace your SSH key with a new one. They're so cheap they might as well be free, and it removes you from worrying about whether anyone has, is, or will be able to get a copy of the private key with the compromised passphrase. Remember, if somebody grabs a copy of your key that you backed up months before you leaked (and changed) your passphrase, the passphrase still gives them access to that key - which is the same as you're using today under a new passphrase.
So just change your key. It's good practice and best practices.
@David-Z has suggested that the time involved in replacing the key is a cost to be considered. I maintain that, since we're talking about keys, that's also negligible, as you can automate the process. The following script took me about 15 minutes to write and test:
for i in $*
cat newkey.pub | ssh -i oldkey username@$i "cat >> ~/.ssh/authorized_keys"
ssh -i newkey username@$i "sed -n '/my_old_key/!p' < ~/.ssh/authorized_keys > ~/.ssh/authorized_keys_tmp && mv ~/.ssh/authorized_keys_tmp ~/.ssh/authorized_keys"
if [ $? -eq 0 ]; then
echo "Successful key replacement for $i"
echo "Key replacement failed for $i"
This script will:
- Use the old key to append the new key to the remote authorized_keys
- Use the new key to remove the old key from the remote authorized_keys
The beauty is that if anything went wrong pushing the new key out, the removal of the old key will fail since it uses the new key, so you're less likely to shoot yourself in the foot.
You'll need to cache your passphrases with ssh-agent so that it doesn't prompt you for these uses of ssh; then just run it with the servers you want to update on the command line:
SSH_AUTH_SOCK=/tmp/ssh-GWE6uxZxn9IS/agent.2016; export SSH_AUTH_SOCK;
SSH_AGENT_PID=2017; export SSH_AGENT_PID;
echo Agent pid 2017;
$ ssh-add oldkey
Enter passphrase for oldkey:
Identity added: oldkey (oldkey)
$ ssh-add newkey
Enter passphrase for newkey:
Identity added: newkey (newkey)
$ ./chssh.sh server1 server2 server3
Successful key replacement for server1
Successful key replacement for server2
Successful key replacement for server3