We consider the certification of temporal quantum correlations using the pseudo-density operator (PDO), an extension of the density matrix to the time domain, where negative eigenvalues are key indicators of temporal correlations. Conventional methods for detecting these correlations rely on PDO tomography, which often involves excessive redundant information and requires exponential resources. In this work, we develop an efficient protocol for temporal correlation detection by virtually preparing the PDO within a single time slice and estimating its second-order moments using randomized measurements. Through sample complexity analysis, we demonstrate that our protocol requires only a constant number of measurement bases, making it particularly advantageous for systems utilizing ensemble average measurements, as it maintains constant runtime complexity regardless of the number of qubits. We experimentally validate our protocol on a nuclear magnetic resonance platform, a typical thermodynamic quantum system, where the experimental results closely align with theoretical predictions, confirming the effectiveness of our protocol.