Your machines could change their IPs for every second of every day and you wouldn't come close to exhausting your /64 subnet for the next billion years.
Won't this break your TCP connections? NAT won't, because it's connection-aware by its nature. And you also get a new "address"(=port) on each new connection, regardless of any setting.
Deprecated addresses still work, they just aren't removed from an interface until there are no more sockets using them.
(Hand waving a bit here with terminology don't shoot me)
Why do network stuff easy, when you can do it hard.