Determine whether the instances sending the most traffic are in the same Availability Zone (AZ) as the NAT gateway. If they're not, then create new NAT gateways in the same AZ as the resource to reduce cross-AZ data transfer charges.
Determine whether the majority of your NAT gateway charges are from traffic to Amazon Simple Storage Service or Amazon DynamoDB in the same Region. If they are, then set up a gateway VPC endpoint. Route traffic to and from the AWS resource through the gateway VPC endpoint, rather than through the NAT gateway. There's no processing or hourly charges for using gateway VPC endpoints.