You have to ensure these rules.

1. NAT Gateway are in the Public Subnet, and set to Public Connectivity Type

2. Route Table on Private Subnet are set to Destination: 0.0.0.0/0 → Target: NAT Gateway

3. Network ACL on both Private and Public Subnet are Set Allow for connection to 0.0.0.0/0 on both Inbound and Outbound Traffic

4. Ensure Private Instance security group's are set Outbound to 0.0.0.0/0 on Outbound traffic or just set to specific Port and Protocol

I found that Point 3 is the solution to the similar problem that you have.