The Gamma constant-stress accelerated degradation model is a natural model for monotonous degradation processes. However, unit heterogeneity often exists in practice, necessitating a more realistic model. This study develops a Gamma process with random effects to accurately capture accelerated degradation data for reliability analysis, encompassing both point and interval estimation. First, the Expectation-Maximization (EM) algorithm is developed to obtain point estimates of the proposed model. Since these estimates are sensitive to initial values, potentially impacting the outcomes, an improved EM algorithm is proposed, which iteratively refines the estimation quality by executing two different M-steps, thereby enhancing overall estimation accuracy. Secondly, given the complexity of the model and the constraint of small sample sizes and limited stress levels, a three-step interval estimation method is devised. This method segregates the parameters into three distinct parts and addresses them individually using the generalized pivotal quantity method, which simplifies the parameter interval estimation process and enhances the estimation accuracy. Finally, simulation studies and a real example of O-rings are presented to demonstrate the effectiveness of the proposed method.