Problema resolvido:
Parece que houve um problema com meu arquivo de chave pública. O PuttyGen criará um arquivo de chave pública que se pareça com:
---- BEGIN SSH2 PUBLIC KEY ----
Comment: "rsa-key-20121022"
AAAAB3NzaC1yc2EAAAABJQAAAIEAhGF6GIuMY8FJ1+CNApnSY1N2YSlkYz72Yvwu
a6N1nFpBklz1+dsIMg4rcTLcF34M/tW5Yz+NUDAw2AEbxQ32FPgw7sAOIXktkYOH
tr7mmimiTjkoSCrJh1kqalPSpi8rglT/Bp67Ql2SZwvUFfMzHISryR0EZC4rXP/u
vObrJe8=
---- END SSH2 PUBLIC KEY ----
No entanto, isso não funcionará, então o que você precisa fazer é abrir a chave em PuttyGen e copiá-la de lá (isso faz com que a chave esteja no formato correto e em uma linha):
ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIEAhGF6GIuMY8FJ1+CNApnSY1N2YSlkYz72Yvwua6N1nFpBklz1+dsIMg4rcTLcF34M/tW5Yz+NUDAw2AEbxQ32FPgw7sAOIXktkYOHtr7mmimiTjkoSCrJh1kqalPSpi8rglT/Bp67Ql2SZwvUFfMzHISryR0EZC4rXP/uvObrJe8= rsa-key-20121022
Cole isso em authorized_keys
, então deve funcionar.