Strain-stiffening is one of the characteristic properties of biological hydrogels and extracellular matrices, where the stiffness increases upon increased deformation. Whereas strain-stiffening is ubiquitous in protein-based materials, it has been less observed for polysaccharide and synthetic polymer gels. Here we show that agarose, that is, a common linear polysaccharide, forms helical fibrillar bundles upon cooling from aqueous solution. The hydrogels with these semiflexible fibrils show pronounced strain-stiffening. However, to reveal strain-stiffening, suppressing wall slippage turned as untrivial. Upon exploring different sample preparation techniques and rheological architectures, the cross-hatched parallel plate geometries and in situ gelation in the rheometer successfully prevented the slippage and resolved the strain-stiffening behavior. Combining with microscopy, we conclude that strain-stiffening is due to the semiflexible nature of the agarose fibrils and their geometrical connectivity, which is below the central-force isostatic critical connectivity. The biocompatibility and the observed strain-stiffening suggest the potential of agarose hydrogels in biomedical applications.