Had the same problem. It looks like it went away after I cleaned up my keychains. Backup your keychains first. I'm not sure why, but I had to re-enter the e-mail passwords and etc. as result of the following procedure (it looks like iCloud keychain got disconnected, so after I enabled it again in iCloud preferences, I got back all my passwords). The only thing that I lost is the "saved" password for my private ssh key (~/.ssh/id_rsa) (luckily I was able to recover it from my memory).
What I did:
1. I switched to single login keychain (had two extra keychains holding the certificates)
2. Created a new empty keychain
3. Made the new keychain default
4. Transferred the certificates to the new keychain
5. Disconnected the old keychain
6. Verified that the signing is OK with Xcode
7. Connected the old keychain (it was renamed to login_renamed.keychain - renamed it back together with login_renamed.keychain-db)
8. Made the old keychain default.
9. Disconnected the keychain created on step 2.
Just in case, people in this thread report that they cleaned up duplicate certificates in their keychains, I can confirm that I remember that I also had something like 10 duplicates that I deleted. Probably that's related/worth trying first.
The signing is still slow. But it no longer takes 4 minutes for the project I'm working on (it has something like 20 frameworks to sign). Something like 20 seconds on Mac Book Pro 13 Late 2011.