Make sure that you don't have a separate firewall running on the VM/server itself, in addition to the cloud's native firewall. Changing cloud firewall rules and dealing with the SSH keys will be useless as the server's firewall will terminate the connections. The only way to see this happening is to check the firewall logs on the server.