A maneira usual de converter chaves entre diferentes formatos é usar os programas de geração de chaves dos programas correspondentes, que geralmente também têm alguma opção de conversão.
No seu caso, uma chave Putty pode ser convertida em outros formatos pelo uso do programa PuttyGen.
A documentação explica como fazer isso em uma GUI maneira (você precisa da chave pública para colar no formato do arquivo authorized_keys ).
Usando as chaves ssh do PuTTY com o OpenSSH no Ubuntu parece mostrar uma forma de linha de comando para fazer isso também:
puttygen /path/to/puttykey.ppk -L > ~/.ssh/id_rsa.pub
(Eu não tentei isso, e um dos comentários lá diz que não funciona assim - dê uma olhada na documentação.)