Such problem should indicate that you are on disconnected network or don't have access to the Windows Update site (http://ctldl.windowsupdate.com/). Windows tries to update its Certificate Trust List (CTL) from the Windows Update site and fails. That's why there is a delay and it seems that configuring system-wide proxy allows Windows to reach the Windows Update site.
Contact your admin and read https://blogs.technet.microsoft.com/configurationmgr/2015/05/19/support-tip-why-cant-i-deploy-this-digital-certificate-security-advisory-with-wsus-or-configuration-manager/
Check this page to learn how to disable CTL's network retrieval:
If you cannot avoid installing this update on disconnected systems,
you can disable the network retrieval of the trusted and untrusted
CTLs. To do this, you disable automatic root updates by using Group
Policy settings. To disable automatic root updates by using policy
settings, follow these steps:
- Create a Group Policy or change an existing Group Policy in the Local Group Policy Editor.
- In the Local Group Policy Editor, double-click Policies under the Computer Configuration node.
- Double-click Windows Settings, double-click Security Settings, and then double-click Public Key Policies.
- In the details pane, double-click Certificate Path Validation Settings.
- Click the Network Retrieval tab, select Define these policy settings, and then clear the Automatically update certificates in the
Microsoft Root Certificate Program (recommended) check box.
- Click OK, and then close the Local Group Policy Editor.
After you make this change, automatic root updates are disabled on
those systems to which the policy is applied. We recommend that the
policy be applied only to those systems that do not have Internet
access or that are prevented from accessing Windows Update because of
firewall rules.