A certificate validation operation took nnn milliseconds and has exceeded the execution time threshold

After installing a new SharePoint 2013 farm, I noticed a few messages in the Windows event log:

A certificate validation operation took 14988.6926 milliseconds and has exceeded the execution time threshold. If this continues to occur, it may represent a configuration issue. Please see http://go.microsoft.com/fwlink/?LinkId=246987 for more details.
Source:	SharePoint Foundation
Event ID:	8321
Level:	Critical

As Microsoft states in their knowlege base article KB2625048:

The SharePoint server does not have access to the Internet, or the server is protected by a firewall that has limited ports open. In this situation, users intermittently experience long delays when they perform certain operations, such as logging in to the site or performing a search. Users may also encounter HTTP timeouts when they perform these operations.

The mean you must either let your server access the internet, what most of the time won't be possible due to policy reasons, or we need a other solution. Good for us that the knowlege base article offers two possible solutions.

Workaround 1

Install the SharePoint Root Authority certificate in the Trusted Root Certification Authorities store. After the root certificate is added to the local certificate store, the certificate validation is no longer performed over the Internet. The below steps will cause the BuildChain to succeed by finding the certificate in the local store, therefore eliminating the need for the retrieval of an object from the network. The following steps have to be completed on each SharePoint server in the farm to add the root certificate to the local certificate store:
Export the SharePoint Root Authority certificate as a physical (.cer) file. Start the SharePoint Management Shell as an Administrator,and then run the following Windows PowerShell commands:

$rootCert = (Get-SPCertificateAuthority).RootCertificate 
$rootCert.Export("Cert") | Set-Content C:\SharePointRootAuthority.cer -Encoding byte

Note This will export the internal root certificate (.cer file) for SharePoint to Drive C. You can copy and use this file on all servers in the farm for importing without having to run the PowerShell commands again. Import the SharePoint Root Authority certificate to the Trusted Root Certification Authorities store. To add the SharePoint Root Authority certificate to the Trusted Root Certification Authorities store, follow these steps:

1. Tap or click Start, type mmc in Start search, and then press Enter.
2. On the File menu, click Add/Remove Snap-in.
3. Under Available snap-ins, click Certificates, and then click Add.
4. Under This snap-in will always manage certificates for, select Computer account, and then click Next.
5. Select Local computer, and then click Finish.
6. If you have no more snap-ins to add to the console, click OK.
7. In the console tree, double-click Certificates.
8. Right-click the Trusted Root Certification Authorities store.
9. Click All Tasks, click Import to import the certificate, and then follow the steps in the Certificate Import Wizard.

Workaround 2

Disable the automatic update of root certificates on the SharePoint Servers. To do this, follow these steps:

1. Under the Computer Configuration node in the Local Group Policy Editor, double-click Policies.
2. Double-click Windows Settings, double-click Security Settings, and then double-click Public Key Policies.
3. In the Details pane, double-click Certificate Path Validation Settings.
4. Click the Network Retrieval tab, select the Define these policy settings check box, and then clear the Automatically update certificates in the Microsoft Root Certificate Program (recommended) check box.
5. Click OK, and then close the Local Group Policy Editor.
6. Run gpupdate /force to make the policy take effect immediately.

Note With auto-update disabled, you may have to monitor KB 931125 for new releases, and then manually update the certificate trust as required.

Implications of disabling automatic root certificate updates

There should not be specific implications to SharePoint because we are using self-signed certificates and manage them ourselves. The SharePoint certificates do have an expiry, but there is a health rule that watches for this and then warns the administrator to update or re-roll them.

The main aspect to consider is for other certificates that are used on the computer (such as SSL certificates, certificates to trust download packages or for SAFER policy, and so on) which are issued from certificates chained to those in the Trusted Root Certification Authorities store.