Se você gerou a chave no Windows usando PuTTYgen e copiou a chave diretamente para a sua estação de trabalho linux, é provável que a chave esteja no formato errado. Você deve ser capaz de usar o PuTTYgen para converter a chave no formato padrão OpenSSH.
Como um complemento, a melhor prática é ter um par de chaves exclusivo para cada dispositivo a partir do qual você se conecta. Basta gerar um novo par de chaves na estação de trabalho linux e adicionar essa chave pública a ~/.ssh/authorized_keys
on example.com
.