We determine the asymptotic relaxation rate of a Brownian particle in a harmonic potential perturbed by quenched Gaussian disorder, a simplified model for rugged energy landscapes in complex systems. Depending on the properties of the disorder, we show that the mean and variance of the asymptotic relaxation rate are nonmonotonous functions of the parameters for a broad class of disorders. In particular, the rate of relaxation may either increase or decrease exponentially compared to the unperturbed case. This implies that disorder may, depending on its properties, both significantly speed up and slow down relaxation. In the limit of weak disorder, we derive the probability distribution of the asymptotic relaxation rate and show that it is Gaussian, with analytic expressions for the mean and variance that feature universal limits. Our findings indicate that controlled disorder may serve to tune the relaxation speed in complex systems.