2 components make up the Lock Time VCO calibration time & PLL Loop Settling Time. For PLL loop settling time: lock time is usually around 5/(2*pi*loop filter BW). Larger loop BW will have faster settling times. There are trade-offs between performance and loop settling times.
Lock time also depends on the loop bandwidth & loop filter. Auto Calibration time is about 1ms for the ADF4371 & ADF4372 PLL+VCO’s but you can use the bypass mode which would significantly reduce the calibration time. See Appnote AN-2005 on the ADI website that details how to reduce locking time for the ADF4371 & ADF4372 family but bypassing Auto Calibration. You can also use ADISimPLL models to simulate lock times for ADI parts.