New algorithms for computing exponential and mixed power-exponential moments of hitting times and accumulated rewards of hitting type for semi-Markov processes are presented. The algorithms are based on special techniques of sequential phase space reduction and recurrence relations connecting exponential moments of rewards.