Muito disso realmente depende do que você está usando os servidores. Essa é uma resposta geral, assumindo um SLA de tempo de segmentação alto.
Se você precisar manter o tempo de atividade durante a mudança, precisará configurar novos servidores com o novo host e, em seguida, configurar a replicação entre os dois servidores. Depois de ter replicação, você pode considerar o uso de balanceamento de carga para colocar os novos servidores em operação lentamente. Dessa forma, se houver uma falha, ela será isolada para apenas alguns usuários (talvez até mesmo migre primeiro um grupo beta).
Se a substituição gradual continuar a funcionar, você poderá mudar para 100% o uso dos novos servidores. Depois de fazer isso, você pode encerrar a replicação e desatribuir os servidores antigos.
É claro que, se sua meta de tempo de atividade for alta, considere a possibilidade de manter alguns dos servidores antigos na replicação e no balanceamento de carga como backup.