Após algumas pesquisas e discussões, dois pequenos programas python foram criados para fazer exatamente o que eu precisava. Ambos foram capazes de despejar todas as senhas que são armazenadas pelo gnome-keyring, incluindo a senha da minha chave ssh. (Isso é seguro, é claro, porque funciona apenas depois que eu destravei meu chaveiro.) Veja esses posts do blog para o código:
Obrigado, Michael Schurter e Liviu. Agora posso simplesmente atualizar minha frase-senha em vez de resolver o problema de substituir minha antiga chave ssh em todos os sistemas em que ela está instalada.