Well, obviously you can't modify the implementation of SignedXml, but it
should be possible to avoid the call to X509Utils._GetOidFromFriendlyName().
This call is coming from CryptoConfig.MapNameToOID(), which, I'm guessing
(but if you could provide a stack trace, please be so kind), is called from
X509Utils.OidToAlgId(), which in turn is called from
RSAPKCS1SignatureDeformatter.VerifySignature() <-
SignedXml.CheckSignedInfo() <- SignedXml.CheckSignature().

There's a bug in how X509Utils.OidToAlgId() and CryptoConfig.MapNameToOID()
interact. CryptoConfig.MapNameToOID() uses two lookup tables, the default
lookup table and the machine lookup table, to match friendly names to OIDs.
The machine table is normally empty, and the default lookup table contains
mappings from all standard .NET algorithm names to OIDs. If both lookups
fail, .MapNameToOID() issues a domain query to resolve the name.

Now, X509Utils.OidToAlgId() calls CryptoConfig.MapNameToOID() with an *OID*
rather than a name, but the latter doesn't know how to handle OIDs. The
default lookup table doesn't contain any OIDs, it contains names. You don't
need a lookup call to match an OID to an OID, after all! Therefore, *any*
call to X509Utils.OidToAlgId() using an OID will invoke a domain query,
hence the slowdown.

That's the long and boring explanation, now on to the solution. The machine
lookup table is editable. If you add "mappings" from OIDs to OIDs, the
slowdown should disappear. The relevant section is in the machine.config of
the framework directory.

The following should do the trick for all framework-implemented hash
algorithms (it does not include third-party ones):

<configuration>
   <mscorlib>
      <cryptographySettings>
         <oidMap>
            <!-- Brought to you by the department of redundancy department -->
            <oidEntry OID="1.2.840.113549.2.5" name="1.2.840.113549.2.5"/>
<!-- MD5 -->
            <oidEntry OID="1.3.36.3.2.1" name="1.3.36.3.2.1"/> <!--
RIPEMD160 -->

            <oidEntry OID="1.3.14.3.2.26" name="1.3.14.3.2.26"/> <!-- SHA1 -->
            <oidEntry OID="2.16.840.1.101.3.4.2.1"
name="2.16.840.1.101.3.4.2.1"/> <!-- SHA256 -->
            <oidEntry OID="2.16.840.1.101.3.4.2.2"
name="2.16.840.1.101.3.4.2.2"/> <!-- SHA384 -->
            <oidEntry OID="2.16.840.1.101.3.4.2.3"
name="2.16.840.1.101.3.4.2.3"/> <!-- SHA512 -->
         </oidMap>
      </cryptographySettings>
   </mscorlib>
</configuration>

If this turns out to be of any help to you, please let us know; I'd be
interested in the results -- in particular if I'm right, because I haven't
tested any of this, but also if this just set you on the right track.