I'm going to answer your initial question first, although it sounds like it's unrelated to the problem you've mentioned
If it has no public IP address, you'll need a way to connect via the private IP - this is typically done using a Bastion Host (which is another instance which does have a public IP, and that you can SSH or RDP into before connecting from the bastion host. Alternatively a VPN connection could be setup connecting your work network or machine to the AWS VPC.
Now, I suspect this isn't your problem, since you were able to connect to the IP address but failed to authenticate. What you should check next is:
- Is this the correct instance that you're connecting to?
- Have you got the correct private key (a new keypair will likely have been generated while changing regions).
One way to check this would be to look at the fingerprint for the key-pair in the AWS EC2 web-console (make sure you've got the correct region open) and then check if it matches the fingerprint for the key stored on your local machine.
This superuser article explains key fingerprints and how to check them:
https://superuser.com/questions/421997/what-is-a-ssh-key-fingerprint-and-how-is-it-generated