Make sure that the connection is only using the key for authentication. The password is not supported. Also, check with your network team, if they can see the logs to find why your server refused the connection attempt by our server.
As for the public key, how did you install it?
And when you tested, did you use a ssh key-pair to test?