Acontece que, como frequentemente é o caso, algo notavelmente estúpido. Eu adicionei manualmente o nome do meu arquivo de chave no meu arquivo de configuração, e dei a chave pública - assim.
Host server
HostName server.address
User myuser
IdentityFile ~/.ssh/id_rsa.pub
Em vez de
IdentityFile ~/.ssh/id_rsa
O que, claro, funciona. (Eu sei que esta linha não é necessária, porque é o nome da chave padrão - eu estava usando um nome de chave diferente)