We needed to apply a fix to curve25519-sha256 key exchange supplied by upstream, but that involved disabling that key exchange method for unpatched 6.6 and earlier versions. OpenSSH 6.7 will fix this when it's released, but in the meantime I suggest applying the same patch to your homebrew client (and perhaps getting the package maintainer to do so as well; I'm not familiar with how homebrew works).
https://lists.mindrot.org/pipermail/openssh-unix- dev/2014-April/032494.html ** Changed in: openssh (Ubuntu) Status: New => Won't Fix -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/1322892 Title: SSH ist unable to negotiate a key exchange method after latest update when curve25519 is required To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/openssh/+bug/1322892/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs