I can't get this to work with AWS and Nat Gateway. I am able to SSH in to to the Private instance (Through Bastion), but I am not able to ssh out from a private instance to a public server that is not within my VPC. The Public server is allowing the Public IP of the NAT for port 22 and I am able to access the internet from the Private instance. I am able to ssh to the public server from another server so I know that it is possible.
However, ssh from the private server behind the NAT to the Public server will not connect and just times out.
I am just not sure if a NAT can handle outbound SSH traffic to the public
Yes, it is possible and I got it working.
The issue I had is since the private servers go through the NAT it is secured by the Network ACL's Inbound Rules even though I am connecting to a server outside the network. So you need to add the Private IP with port 22 access to the Network ACL's Inbound Rules. Or you can add the IP range of your internal subnets which will allow all internal private servers which is useful if your servers are load balanced as they will come and go.