If the magnitude and range is that small, normalizing should definitely help out. A default diagonal of 1e-6 is added internally to stabilize the Cholesky decomposition. If it’s making no difference that might be something to check into as well.
The speed of the GP depend pretty much entirely on the dimension of the covariance matrix. If that doesn’t change from run to run, then that speed should be a constant.