Age of Information (AoI) has attracted much attention recently due to its capability of characterizing the freshness of information. To improve information freshness over fading channels, efficient scheduling methods are highly desired for wireless transmissions. However, due to the channel instability and arrival randomness, optimizing AoI is very challenging. In this paper, we are interested in the AoI-optimal transmissions with rate-adaptive transmission schemes in a buffer-aware system. More specifically, we utilize a probabilistic scheduling method to minimize the AoI while satisfying an average power constraint. By characterizing the probabilistic scheduling policy with a Constrained Markov Decision Process (CMDP), we formulate a Linear Programming (LP) problem. Further, a low complexity algorithm is presented to obtain the optimal scheduling policy, which is proved to belong to a set of semi-threshold-based policies. Numerical results verify the reduction in computational complexity and the optimality of semi-threshold-based policy, which indicates that we can achieve well real-time service with a low calculating complexity.