Cholesky decomposition also has a complexity of $O(n^3)$ operations, so it has the same computational scaling properties as Gaussian Process regression. If you want to reduce time complexity, you could investigate a sparse approximation of the least-squares support vector machine (LSSVM) which is equivalent to dual ridge regression, which I have found useful, see e.g.
Gavin C Cawley and Nicola LC Talbot, "Improved sparse least-squares support vector machines", Neurocomputing, volume 48, number 1, pages 1025-1031, 2002
Gavin C. Cawley and Nicola LC Talbot, "A greedy training algorithm for sparse least-squares support vector machines", International Conference on Artificial Neural Networks—ICANN 2002, pages 681 686, 2002
If greedy selection of representation vectors is too slow, simply picking a subset of the data at random tends to work quite well (as long as all of the training data appear in the loss function).
I am not very keen on support vector regression as the $\epsilon$-insensitive loss function doesn't have a straightforward probabilistic interpretation, which is often important in regression applications.