Change address on every DHCP renewal

For devices used by humans (workstations, phones, etc.): Configure this to happen at ~4 AM local time, and very few people will care. In the event that you do need some humans working those hours (e.g. at hospitals), use the next solution instead, or schedule those humans' devices to force a re-discover at a different time (if feasible).

For devices that are serving traffic, or otherwise cannot suffer a total site outage all at once: Spread the DHCPNAKs over several hours during your daily trough (the period when usage is lowest every day), such that you lose no more than one device every few minutes or so. If your error budget does not allow for this, then only flip over a fraction of all devices every day (preferably, split the devices into stable cohorts so that every device is flipped once every few days). If you do not have an error budget, then on paper, your requirements are not compatible with doing this at all (see next item). You should consider whether or not you really intend to provide that level of availability, and for that matter whether you have the necessary resources to do so.

For devices that absolutely, positively must not go down under any circumstances: Obviously, you cannot do this at all, because even the tiniest blip is a catastrophic failure, under this standard of availability. Instead, you should be hardening the network so that it does not go down (e.g. put the router on a UPS, get multiple discontiguous fiber links from separate ASes, etc.). Probably it's also worth the bother of configuring the device with a static address just in case, but that's almost the least important part. You may have noticed that this is extremely expensive. That's the point. "Absolutely must not go down ever" is a very high bar. You are not going to get there by clever configuration of software alone.