SSH pede senha para algumas chaves apesar de ser adicionado ao agente

Question

Eu tenho dois servidores nos quais me conecto usando autenticação de chave pública SSH, com chaves diferentes. A configuração é assim:

Host server1
  IdentityFile /path/to/key
  IdentitiesOnly yes

Host server2
  IdentityFile /path/to/other/key
  IdentitiesOnly yes

Eu adiciono as duas chaves ao agente e verifico via ssh-add -l que ambos estão presentes. No entanto, um funciona, mas o outro não:

$ssh -v server1
...
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /path/to/key
debug1: Server accepts key: ...
debug1: Authentication succeeded (publickey).

$ssh -v server2
...
debug1: Next authentication method: publickey
debug1: Trying private key: /path/to/other/key
debug1: key_parse_private2: missing begin marker
debug1: key_parse_private_pem: PEM_read_PrivateKey failed
debug1: read PEM private key done: type <unknown>
Enter passphrase for key '/path/to/other/key': 

O SO é o Ubuntu 14.04, a saída de ssh -V é OpenSSH_6.6.1p1 Ubuntu-2ubuntu2.3, OpenSSL 1.0.1f 6 Jan 2014 .