The random phase approximation of time-dependent auxiliary density functional theory (TDADFT) is rederived from auxiliary density perturbation theory. Our exhaustive validation of TDADFT reveals an upshift of the excitation energies by ∼0.1 eV with respect to standard time-dependent density functional theory. For the computationally efficient implementation of TDADFT, floating point operation optimized three-center electron repulsion integral recurrence relations and their double asymptotic expansions are implemented into the Davidson solver. The computational efficiency of TDADFT is benchmarked with four sets of molecules comprising alkanes, fullerenes, DNA fragments, and zeolites. The results show that TDADFT has a computational scaling between 1.3 and 1.9 with respect to the number of basis functions, which is lower than the scaling of standard time-dependent density functional theory. Due to its computational simplifications, TDADFT is particularly well suited for Born-Oppenheimer molecular dynamics simulations. As illustrative examples, we present the temperature effects on the gas-phase absorption spectra of benzene, naphthalene, and anthracene.