A chave aqui é a atualização do Mavericks para o El Capitan. Acontece que o cliente ssh foi atualizado em El Capitan, então quando ele tenta se conectar a um servidor ssh, ele agora usa um tipo de chave diferente ao invés de "ssh-rsa".
Neste caso, o ssh tenta usar "ecdsa-sha2-nistp256". Em um sistema mais novo, se você executar "ssh-keyscan" no domínio, ele irá citar tanto o tipo de chave ssh-rsa quanto o ecdsa-sha2-nistp256:
myname@myhost-1:~$ ssh-keyscan real.hostname.com
# real.hostname.com SSH-2.0-OpenSSH_6.6.1
real.hostname.com ecdsa-sha2-nistp256 k8DaAFOzRyv0kbP8Ua48IIk8DaAFOzRyvAAIbmlzdHAyNTYAAABBBAOq0InBTTdCqbaackF5biy0QghSFZBV/MRoL936yOAXgPAnZlHl+zQ5weK7nM2UNt2qGxqWKLSZ6gE6slZnQkw=
# real.hostname.com SSH-2.0-OpenSSH_6.6.1
real.hostname.com ssh-rsa k8DaAFOzRyv0kbP8Ua48IIk8DaAFOzRyvk8DaAFOzRyv0kbP8Ua48IIk8DaAFOzRyvFq6UNxndgThogOpKGYHK0HpmK1niGPBdNVyo9Q8zX//ms3joRH+tvL0RigJ+i5f0qSUjK2j80BYyCjnCXkYJ+k8DaAFOzRyv0kbP8Ua48IIiXT652b2WxJJwPqAvz70Xez1ToFxsIl8H0noUNTmlXRsfY0G5gX+HGXoLuLsr9VEghX2oyGCrv7Dpdh+tiMDXQqz0R4yhOa0iAojv+SVqbzArT8/AxC8VzuNDww6Fi96rxK1vaFg9SJEegwAZzWcbUFopA4cb8r7sQ5tHG56L5zX9/Yadg4/Pf02O6dP62M1rW7x6VoG/gEa72axqV/izm7/ws7SASsiKtHKRijf
Quando a versão mais recente do ssh tenta corresponder a sequência de tipo de chave ecdsa-sha2-nistp256 à sequência de tipo de chave ssh-rsa, ela falha, em vez de reconhecer que são dois tipos de chaves diferentes para a mesma máquina.
Eu considero isso um bug, mas não tenho ideia de onde o publiquei.