I can't connect to my Amazon EC2 instance from OSX 10.9.3, but it works with Ubuntu, however the SSH version is the same on both. I've set everything right, because it works with my Ubuntu laptop on the same network and everything...
Andrews-Mac-Pro:~ andrew$ /usr/local/bin/ssh -v -i ~/.ssh/ec2.pem ubuntu@54.72.156.XXX
OpenSSH_6.6, OpenSSL 1.0.1i 6 Aug 2014
debug1: Reading configuration data /usr/local/etc/ssh/ssh_config
debug1: Connecting to 54.72.156.XXX [54.72.156.XXX] port 22.
debug1: Connection established.
debug1: identity file /Users/andrew/.ssh/ec2.pem type -1
debug1: identity file /Users/andrew/.ssh/ec2.pem-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.6
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6.1p1 Ubuntu-2ubuntu2
debug1: match: OpenSSH_6.6.1p1 Ubuntu-2ubuntu2 pat OpenSSH* compat 0x04000000
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5-etm@openssh.com none
debug1: kex: client->server aes128-ctr hmac-md5-etm@openssh.com none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
Read from socket failed: Operation timed out
I had this same problem and found that resetting the MTU on my network interface to Standard (1500) fixed the problem!