New algorithms for computing power moments of hitting times and accumulated rewards of hitting type for semi-Markov processes are developed. The algorithms are based on special techniques of sequential phase space reduction and recurrence relations connecting moments of rewards. Applications are discussed as well as possible generalizations of presented results and examples.