We study the mechanical relaxation behavior of human red blood cells by observing the time evolution of shape change of cells flowing through microchannels with abrupt constrictions. We observe two types of relaxation processes. In the first fast process (tau(1) similar to 200 ms) the initially parachute shaped cells relax into cup-shaped cells (stomatocytes). These cells relax and reorient in a second relaxation process with a response time of tau(1/2) similar to 10 s into the equilibrium discoid shapes. The values for the relaxation times of single red blood cells in the population scatter significantly within the cell population between 0.11 s < tau(1) < 0.52 s and 9 s < tau(1/2) < 49 s, respectively. However, when plotting tau(1/2) against tau(1), we find a linear relationship between the two timescales and are able to relate both to the elastic properties of the spectrin cytoskeleton underlying the red cell's plasma membrane. Adenosine Triphosphate (ATP) enhances dissociation of spectrin filaments resulting in a reduced shear modulus. We modify the cytoskeleton connectivity by depletion and repletion of ATP and study the effect on relaxation. Both the linear relationship of timescales as well as the ATP dependence can be understood by theoretical models.