I would try this in stages...
this are just my thoughts about it.
Set up heavy forwarders that accept data inputs with the new certificate and output them with the old to you existing environment.
Replace the old certs (you hopefully configured them in a custom app like org_all_forwarderoutputs) and push them with your deployment server out to your forwarders. Make sure they are pointing now to the heavy forwarders.
Wait till all forwarders are updated. In this time indexers will accept the data from the not yet updated and heavy forwarders from the already updated.
Update your indexers to the new certs and also update the outputs from your heavy forwarders to the new certs
Deploy your org_all_forwarderoutputs again to your forwarders pointing directly to the indexers with the new certs
Delete the heavy forwarders after all forwarders switched back to the indexers.
I would highly recommend to test that in a smaller environment before...
... View more