what would you use instead?

AWS NAT Gateway pricing is so outrageous that smart people came up with a peculiar hybrid:

https://www.lastweekinaws.com/blog/an-alternat-future-we-now...

I wouldn't use it in production (some companies do, for internal things) but the very fact it exists speaks volumes.

a tiny ec2 box that provides NAT for about $3/mo.