The key here is the upgrade from Mavericks to El Capitan. It turns out that the ssh client has been upgraded in El Capitan, so when it attempts to connect to a ssh server, it now uses a different key type instead of "ssh-rsa".
In this case ssh attempts to use "ecdsa-sha2-nistp256". On a newer system, if you run "ssh-keyscan" on the domain, it will spit out both the ssh-rsa key type and 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
When the newer version of ssh attempts to match the ecdsa-sha2-nistp256 key-type string to the ssh-rsa key-type string it fails, rather than recognizing that they're two different key types for the same machine.
I consider this a bug, but I have no idea where I'd post it.