Se você tiver criptografado sua chave privada (fornecendo uma frase secreta ao criá-la), será necessário descriptografá-la antes de poder efetuar login em sistemas remotos. É possível que você estivesse usando um agente ssh no sistema local para armazenar a chave não criptografada. Quando você reiniciou, a chave teria sido liberada da memória do agente. Se for esse o caso, você precisará adicionar novamente a chave ao agente (usando algo como ssh-add) e, em seguida, você deve conseguir efetuar login sem fornecer uma senha ou frase secreta, supondo que a chave pública esteja em vigor, permissões e propriedade corretas, etc.
O fato de o agente ssh estar ou não em execução depende do seu ambiente. Acredito que a maioria dos ambientes de desktop hoje em dia executa a sessão de desktop sob o ssh-agent, então o ssh-add "simplesmente funciona".