Walking mechanisms are very important for legged robots to ensure their stable locomotion. In this research, Klann-linkage is suggested as a walking mechanism for a water-running robot and is optimized using level average analysis. The structure of the Klann-linkage is introduced first and design variables for the Klann-linkage are identified considering the kinematic task of the walking mechanism. Next, the design problem is formulated as a path generation optimization problem. Specifically, the desired path for the foot-pad is defined and the objective function is defined as the structural error between the desired and the generated paths. A process for solving the optimization problem is suggested utilizing the sensitivity analysis of the design variables. As a result, optimized lengths of Klann-linkage are obtained and the optimum trajectory is obtained. It is found that the optimized trajectory improves the cost function by about 62% from the initial one. It is expected that the results from this research can be used as a good example for designing legged robots.