This issue is covered pretty well by blogs in the context of SSMS (Dan Jones and Euan Garden) and in the context of SSIS service it has a KB article. But I still see forums posts and private questions that show that not all SSIS users are aware of it or realize that the same issue can cause SSIS package execution delays, especially when running as an Agent Job or another non-interactive service.
The issue in short: managed SQL Server assemblies are signed with Microsoft certificate, and when the application starts, .NET validates this key, including checking CRL (certificate revocation list - remember when Verisign issued two "Microsoft" certificates to unknown party? - CRL helps mitigate the harm from such mistakes). CryptoAPI tries to retrieve CRL using HTTP request (in case of SQL certificate - to crl.microsoft.com), and usually everything is fine. Even if this site is not accessible (e.g. you don't have internet connection at all), it is not a problem: CryptoAPI gets an error from network, and simply ignores the CRL.
When does it cause a problem? If the network (or firewall) does not reply with the error code telling CryptoAPI that the site is not accessible, but silently drops the packets. This causes the certificate check to timeout after 15 seconds. If multiple certificates are involved, the delays add up, e.g. 30 seconds in case of two certificates.
Unfortunately, the fix for this issue requires upcoming .NET 3.5. For now, you have to configure the network and firewall to behave correctly, i.e. either allow access to crl.microsoft.com, or quickly report the error.
Why did I write in the beginning that this affects execution via Agent more often than interactive users? Often firewalls are working correctly for interactive and domain users but behave differently for non-interactive or local users. E.g. some firewalls require proxy settings to be configured (manually or often using logon scripts), so everything is fine for interactive users. But the settings for Agent service user account or Agent Proxy user account might not be configured properly, which causes the delays when the job is executed. So if your packages takes 5 seconds when running interactively, and 35 when run as a job, you now know why.
Update (2010/10): The ability to avoid certificate validation is backported to .NET 2.0 as hotfix. You just have to have the .Net hotfix 936707 or later installed. You can check the .Net file C:\Windows\Microsoft.NET\Framework\v2.0.50727\MsCorWks.dll to make sure it is higher than the 876 revision (2.0.50727.876 or later) if you are unsure the patch is installed.
To avoid the certificate check, a new option is also required in application configuration file (.NET guys did not want to break compatibility for those who do use these certificates). If you have SSIS 2008 or later, the config change is already included in the config files for all SSIS executables. For SSIS 2005 and if you have a custom executable that loads SSIS runtime, you might have to edit application config file, and add the highlighted line under configuration / runtime. E.g. here is dtexec.exe.config from SSIS 2008: