Consider computing the gcd from the primitive operations of addition, subtraction, division, and remainder. The best known deterministic algorithm is the Euclidean algorithm, which takes logarithmic time in the magnitude of the smaller input (where "time" here means the number of calls to the primitive operations), i.e., linear in the length of the input. This has been conjectured to be optimal.
Whereas, there is a nondeterministic algorithm (Pratt's algorithm) which takes time $\log \log n$, where $n$ is the magnitude of the smaller input. So as far as anyone knows, there's an exponential gap between the best deterministic and nondeterministic complexity.
So of course this is not time on a Turing machine, but it does show the possibility for more dramatic speedups with very natural notions of time.