Shrinking subnets in a an AWS VPC
Solution 1:
Implement IPv6. One /64 per subnet is effectively unlimited addresses. Use a /56 from AWS for 256 /64s.
Unfortunately, I don't have a v4 option, especially not with the restriction of keeping the same range and staying running.
Classic example of a v4 address plan appearing large, until it needs to be further subdivided into new nets. Don't underestimate work spent in counting hosts and defragmenting ranges.