In this paper we propose a design of a class of robotic legs (known as ``Ninja legs'') that enable amphibious operation, both walking and swimming, for use on a class of hexapod robots. Amphibious legs equip the robot with a capability to explore diverse locations in the world encompassing both those that are on the ground as well as underwater. In this paper we work with a hexapod robot of the Aqua vehicle family (based on a body plan first developed by Buehler et al. \cite{georgiades2004aqua}), which is an amphibious robot that employs legs for amphibious locomotion. Many different leg designs have been previously developed for Aqua-class vehicles, including both robust all-terrain legs for walking, and efficient flippers for swimming. But the walking legs have extremely poor thrust for swimming and the flippers are completely unsuitable for terrestrial operations. In this work we propose a single leg design with the advantages of both the walking legs and the swimming flippers. We design a cage-like circular enclosure for the flippers in order to protect the flippers during terrestrial operations. The enclosing structure also plays the role of the walking legs for terrestrial locomotion. The circular shape of the enclosure, as well, has the advantages of an offset wheel. We evaluate the performance of our design for terrestrial mobility by comparing the power efficiency and the physical speed of the robot equipped with the newly designed legs against that with the walking legs which are semi-circular in shape. The swimming performance is examined by measuring the thrust generated by newly designed legs and comparing the same with the thrust generated by the swimming flippers. In the field, we also verified that these legs are suitable for swimming through moderate surf, walking through the breakers on a beach (and thus through slurry), and onto wet and dry sand.