Após um rápido tutorial sobre como a autenticação de chave RSA funciona, encontrei minha resposta:
Parece que não entendi como funciona uma chave pública / privada. Eu não fiz backup da chave privada, apenas a chave pública. Eu estou tentando restaurar a chave pública para o meu arquivo id_rsa quando eu deveria estar restaurando a chave privada. Portanto, estou ferrado.
Lições aprendidas? Faça o backup das chaves id_rsa e id_rsa.pub. NÃO apenas a chave id_rsa.pub.