Eu tentei algumas coisas, entre outras ssh-add, redefinindo o SSH (excluindo .ssh / no servidor, e tal, mas sem sorte. Então, descobri que tinha que dormir por uma noite. ajudou! Por que? Eu acho que o agente ssh em execução no servidor tinha algo em seu cache que foi atualizado mais tarde naquela noite com os valores agora adequados. De qualquer forma, agora funciona como um encanto. Para finalizar, ele fez isso (Ubuntu 16.04 no host local, 14.04 no servidor).
# on local host:
$ ssh-keygen
# (yes, overwrite the default file, and let the passphrase be empty)
$ ssh-copy-id ***.***.*.**
# (insert proper server IP address)
# now test
$ ssh ***.***.*.**
# this should have erected in .ssh/ on the server:
# -rw------- 1 *** *** 2000 aug. 11 09:55 authorized_keys
# no other magic going on! :)