This is not the answer to all occurences of the issue but try the following;
Now try SSMS again, was it faster? Either way re-check the setting to be safe.
Ok so here is what is happening. SSMS has a high percentage of managed code, all of this code is signed when we ship it. At start up (if this setting is checked) the .Net Runtime tries to contact crl.microsoft.com to ensure that the cert is valid(there were some fake certs issued in Microsoft's name a while back so this is a very valid concern). If there is no internet connection or there is a problem contacting the certificate revocation list server then this will delay SSMS startup.
Now this problem is not unique to SSMS, it actually applies to all managed code and flipping the switch switches off this check for ALL managed code on the machine which may not be a good idea, but at this time I don't know of a way to switch off the check on a per app basis, there are some folks looking however.
There have been several internal discussions on this and some external ones as well.