It does not matter if you lose your SSH private keys though as they are disposable and you can just generate new ones, it's not like they are being used to encrypt anything. To add your new public key to your servers you either get someone else who can SSH in and su to root to do it for you or you login locally (via kvm or similar). Larger deployments most likely have some centrally managed system for dealing with SSH keys.