We define authenticated video as decoded video that results from those received packets whose authenticities have been verified. Generic data stream authentication methods usually impose overhead and dependency among packets for verification. Therefore, the conventional rate-distortion (R-D) optimized video streaming techniques produce highly sub-optimal R-D performance for authenticated video, since they do not account for the overhead and additional dependencies for authentication. In this paper, we study this practical problem and propose an Rate-Distortion-Authentication (R-D-A) optimized streaming technique for authenticated video. Based on packets' importance in terms of both video quality and authentication dependencies, the proposed technique computes a packet transmission schedule that minimizes the expected end-to-end distortion of the authenticated video at the receiver subject to a constraint on the average transmission rate. Simulation results based on H.264 JM 10.2 and NS-2 demonstrate that our proposed R-D-A optimized streaming technique substantially outperforms both prior (authentication-unaware) R-D optimized streaming techniques and data stream authentication techniques. In particular, when the channel capacity is below the source rate, the PSNR of authenticated video quickly drops to unacceptable levels using conventional R-D optimized streaming techniques, while the proposed R-D-A Optimization technique still maintains optimized video quality. Furthermore, we examine a low-complexity version of the proposed algorithm, and also an enhanced version which accounts for the multiple deadlines associated with each packet, which is introduced by stream authentication