It appears newer linux sshd configs (fedora 22) by default include a smaller set of key exchange based mechanisms that they have turned on. This means that it gives errors saying it is unable to connect to the server. To fix this you need to enable some of the older key exchange mechanisms, Adding this line