Parece que você precisa carregar a chave privada no PuTTY.
As chaves privadas são puramente do lado do cliente e específicas do aplicativo - as chaves não são transferidas para o servidor a qualquer momento, como você evitou em seu comentário acima. Cada cliente SSH precisa saber onde procurar sua chave privada, para que possa ser usado no processo de autenticação. Você deve saber que a chave privada deve nunca deixar a máquina em que foi gerada. A chave privada é sua identidade e deve ser protegida. A chave pública, no entanto, pode ser compartilhada por vontade própria, postada on-line, tatuada no seu posterior, seja qual for.