AWS is making continual improvements in this area.
Thankfully, in my case, I have a very steady flow of data so I don't expect too many cold starts.
One thing though, does your lambdas need both public and private access? Else you can place them in a subnet for private only, since the slow part is the ENI for the Nat Gateway.
[1] https://twitter.com/jeremy_daly/status/1068272580556087296
So, 10+ seconds cold start, and 200 + 200-300ms (around 500-600ms avg) calls to the Lambda function. Complete garbage for our application at least (I imagine using it for background processing might not be an issue with latency).
Switched over to EC2, less than 200ms response total, no cold starts.
We've tried this and it helps somewhat but when AWS attempts to scale your function based on load, cold starts re-appear. We've moved away from Lambdas where a dependable response time is required.
If you are experiencing cold starts it means that function is not used very often. If it's not used very often that likely means it's not user facing (or something less important like a Terms of Service page). If that's the case, why do you need instant response times?
With delays as bad as 8+ seconds for ENI attachment, this is a significant holdback (https://medium.freecodecamp.org/lambda-vpc-cold-starts-a-lat...)
You can basically replace all HTTP-API Lambdas with it, because it allows direct access to DynamoDB.