Many thanks, problem solved 
Whilst the gpg --refresh-keys didnât actually solve the problem it certainly pointed me in the right direction. Our firewall was blocking outgoing tcp 11371 which appears to be required for the key servers. Modified the firewall to allow this and the âApply Configâ is now back to taking only a few seconds. I guess something changed between 6.12.65-20 and 6.12.65-23 which now required this access.