Cold start performance is improving significantly as the Lambda fleets migrate to Firecracker technology: https://aws.amazon.com/blogs/aws/firecracker-lightweight-vir...
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.
AWS is making continual improvements in this area.