What is the best approach to serve high bandwidth traffic with AWS NAT Gateway
If the burst bandwidth of a NAT Gateway doesn't meet your requirements (currently 45Gbps), you will most likely have to configure a NAT instance.
(Bear in mind you can have one NAT Gateway per AZ)
The bandwidth of a NAT instance is dependent upon the the instance type you use.
There is more information about the comparison here
I would stay away from deploying your services in a public subnet unless it's absolutely necessary.