Sometimes it takes 4 minutes and a few hours later 6 minutes.

Which version of PE are you using? Versions that do not use lockless deployment are constrained by the slowest catalog compilation cycles because they have to wait for the JRuby pool to idle before acquiring the deployment lock.

puppet 7.20 2021

Ok, rising catalog compile times could be feeding back into your deployment latency then. Lockless deployment stabilized and became the default in the 2023 LTS.