Para o EC2, primeiro verifique seus grupos de segurança de rede. Normalmente, a saída é aberta, mas a entrada é completamente fechada. Você configurou a porta 22 e a configurou para seu endereço IP ou foi aberta?
Além disso, verifique o que acontece quando você digita sudo service ssh restart
. Nenhuma mensagem de erro costuma ser boa.
Você tem mais de uma instância? Você pode ssh de um para o outro?
Além disso, verifique se você está usando o endereço IP público