This is where Infrastructure as code comes into play. If you can blow away the entire lot and stand back up an entire fresh set of machines where you have an immutable / declarative way of launching everything you could save a massive amount of time. Ok bare metal is a bit harder and getting up the base hypervisor layer if you're on-premise will take a short while, but after that IAC would save you a fair old chunk of time.
Terraform ftw, or Heat if you're an OpenStack shop.
Biting the hand that feeds IT
