As chaves não precisam ser criadas no cliente. As chaves nem precisam ser criadas com o mesmo sistema operacional. Se você usar as ferramentas corretas, poderá converter uma chave gerada pelo gerador de chaves Putty em uma chave de formato OpenSSH.
Seu problema é mais provável porque o OpenSSH e alguns outros clientes SSH são muito exigentes quanto às permissões das chaves privadas.
Dependendo de como você transferiu a chave privada para o cliente, as permissões da chave podem ser diferentes do servidor e erradas. A chave privada deve ser sempre 0600
ou -rw-------
.
Você verá um aviso sobre isso no cliente se passar a opção -v
para ssh quando se conectar. Ele irá reclamar sobre as permissões na chave privada, ou possivelmente no diretório que contém a chave privada.