Existem várias soluções:
Uma avenida é um cofre de chaves específico, seja um dispositivo baseado em hardware, um módulo de segurança de hardware ou um equivalente baseado em software.
Outra é simplesmente revogar a chave antiga e gerar um novo par de chaves privada / pública quando a situação surgir. Isso muda um pouco o problema de manter a segurança de chave para proteger o nome de usuário / senha da conta com o provedor de certificado e seus procedimentos para reemissão. A vantagem é que a maioria das organizações já possui uma solução de gerenciamento de conta privilegiada, por exemplo, 1 2
Existem várias formas de armazenamento off-line, desde a impressão de uma cópia impressa do par de chaves privado e público, incluindo a senha (mas que será uma cadela para restaurar) até simplesmente armazená-las em mídia digital classificada para muito tempo de armazenamento.
Locais realmente ruins são o GitHub, sua equipe WiKi ou um compartilhamento de rede (e você tem a ideia).
Atualização de 2015/4/29: Keywhiz parece uma abordagem interessante também.