In the Internet of Vehicles (IoV), service migration is regarded as a key technique to address the service disruption problem of mobile vehicles. However, the complexity of vehicle mobility patterns and the potential tracking of vehicle trajectories by malicious attackers pose severe challenges for developing effective service migration strategies. To this end, this paper proposes a secure and efficient service migration method (STG-MOPSO). Firstly, we construct a hybrid spatio-temporal trajectory prediction model that integrates spatial and temporal dependencies of vehicle trajectories, thereby enhancing prediction accuracy. Secondly, a dynamic pseudonym update mechanism is designed to secure vehicle privacy from the communication level. Finally, the service migration problem is modeled as a multi-objective model that minimizes the delay of the pseudonym mechanism and the service delay, and the multi-objective particle swarm algorithm is used to optimize the solution. Experiments show that the proposed methodology outperforms existing techniques, demonstrating its effectiveness in IoV.