Auth Certificate Replication between AD sites.
Note that there is an edge case where a new Auth certificate will NOT successfully replicate to Exchange servers in another site and that is if there is no direct AD site link between Exchange sites. e.g. ExchangeSite1-> non-Exchange AD Site -> ExchangeSite2
You would see an Event 2005 - MSExchange Certificate Deployment
Federation or Auth certificate not found: <thumbprint>. Unable to find the certificate in the local or neighboring sites. Confirm that the certificate is available in your topology and if necessary reset the certificate on the Federation Trust to a valid certificate using Set-FederationTrust or Set-AuthConfig. The certificate may take time to propagate to the local or neighboring sites.
You can export the cert (with private key) and import onto a single Exchange server on the other site and Exchange will take it from there.