In general, cells move on a substrate through extension and contraction of the cell body. Though cell movement should be explained by taking into account the effect of such shape fluctuations, past approaches to formulate cell-crawling have not sufficiently quantified the relationship between cell movement (velocity and trajectory) and shape fluctuations based on experimental data regarding actual shaping dynamics. To clarify this relationship, we experimentally characterized cell-crawling in terms of shape fluctuations, especially extension and contraction, by using an elasticity-tunable gel substrate to modulate cell shape. As a result, an amoeboid swimmer-like relation was found to arise between the cell velocity and cell-shape dynamics. To formulate this experimentally-obtained relationship between cell movement and shaping dynamics, we established a persistent random deformation (PRD) model based on equations of a deformable self-propelled particle adopting an amoeboid swimmer-like velocity-shape relationship. The PRD model successfully explains the statistical properties of velocity, trajectory and shaping dynamics of the cells including back-and-forth motion, because the velocity equation exhibits time-reverse symmetry, which is essentially different from previous models. We discuss the possible application of this model to classify the phenotype of cell migration based on the characteristic relation between movement and shaping dynamics.