Forming a stable cluster structure with minimum cost is essential to develop an efficient and reliable communication infrastructure for connected and automated vehicles (CAVs). In this paper, a novel mobility prediction-based efficient clustering scheme (MPECS) is proposed. The basic idea of MPECS is to divide the whole region into distinct areas using Voronoi diagram; so that each vehicle can predict its own longevity and cost of being the cluster head in its current area. MPECS introduces a novel combined metric called the vehicle lifetime value to characterize the vehicle impact on both clustering stability and cost. An analytical analysis is discussed to explore the parameters set that improves the overall performance of MPECS. Also, performance evaluation via simulation is presented to evaluate MPECS compared to four existing clustering schemes for VANETs. The conducted evaluations show a close agreement between simulation and analytical results and demonstrate that MPECS can significantly improve the stability of the clustering architecture with minimal overhead.