We are in the process of making a number of significant changes to our
internal network. At the moment, an amcheck on 52 machines, which
ultimately reports no problems, is taking over 6 minutes. Historically,
when no machines were down etc, this took less than 1 minute.

How can I troubleshoot what is causing this slowness?

-- 
One of the main causes of the fall of the roman empire was that, lacking
zero, they had no way to indicate successful termination of their C
programs.