Amazon NAT instances went the way of a DoDo Bird (now extinct)

I have many Terraform modules where I use an AMI provided by Amazon specifically designed to use as a NAT Instance.

Amazon has decided they will no longer provide an EC2 AMI NAT image.

I have test code where I try to configure an Amazon Linux2 with a bootstrap that configures the NAT instance to enable forwarding between private networks and the internet (NAT). I have also tried configuring an Amazon Linux 2023 as a NAT instance. Both fail to forward private network traffic to the internet.

I am doing something wrong with the Bootstrap I assume, because if I configure the test Terraform Module to use an Amazon NAT Gateway the server in a private network can update and install packages from the internet, whereas a NAT instance fails.

Can anyone point me to an article or repository that properly uses Terraform code that configures any OS (Ubuntu or Amazon linux preferable) into a working NAT instance?