We investigated slow relaxations of the magnetostriction and residual magnetostriction of the phase-separated system (Eu$_{1-x}$Gd$_{x}$)$_{0.6}$Sr$_{0.4}$MnO$_3$, in which the metamagnetic transition from a paramagnetic insulating state to a ferromagnetic metallic state is accompanied by a lattice shrinkage. The relaxations are well fitted by a stretched exponential function, suggesting the strong frustraction between the double exchange interaction and Jahn-Teller effect. We have revealed that the Gd substitution suppresses the frozen phase-separated phase at low temperatures and stabilizes the paramagnetic insulating state in the dynamic phase-separated phase at intermediate temperatures. The former origin would be the randomness effect and the latter would be the suppression of the double exchange interaction.