Currently, due to the high scalability and global coverage of space information network (SIN), more service providers and users are willing to provide or subscribe to personal services through the satellite network. However, the messages are transmitted in public satellite-ground links, which makes access users vulnerable to various forms of attacks. Existing authentication protocols do not meet the expected security and short delay requirements to ensure the security of real-time user access and the confidentiality of communication content. Moreover, with the development of quantum computers, the difficult problems such as ECDLP and DLP have also been proven to be solvable in polynomial time, leading to new threats. Therefore, in this paper, we propose a provably secure and anti-quantum authentication protocol based on randomized RLWE. The protocol not only meets the pre-defined security requirements, but also reduces the total delay of the authentication phase based on the pre-negotiation and fewer authentication transmission. In addition, a concise handover scheme is designed for signal handover scenarios caused by satellite dynamic topology. Further rigorous formal and informal security proofs and performance analysis show that our proposed protocol is more applicable to SIN, while ensuring higher security and resisting various attacks with lower authentication delay.