Work done by friction force

We get tired when we walk because we are moving our whole bodies up and down as we move forward, and this takes energy. Moreover, each time we take a step, we tend to stop our motion slightly and then restart it again. We aren't moving the most efficiently. If our bodies were shaped like wheels, we could take advantage of that static friction to keep moving along flat ground without expending much energy.

Newton's third law. When you push back and down, the ground pushes foward and up. With no friction you would just slip instead. Also there is internal friction in the body, and expended energy to gain potential gravitational energy when you shift your center of mass up

The way the work defined in physics is not one to one correlated with people getting tired. In fact, "getting tired" is a bit confusing. Let's replace that phrase with "muscles spend energy".

Example 1 - Climbing a ladder; work done by the climber is positive and muscles spend energy.

Example 2 - Holding a mass above your head; work done by the holder is zero and muscles spend energy. Or as mentioned in one of the comments, just standing still requires zero work yet muscles spend energy.

Example 3 - Pushing a car (trying to stop) that is moving; work done by the pusher is negative and muscles spend energy.

Coming to your question. When we walk we push our feet backward therefore static friction is in forward direction, that is, in the direction the of walk. So, in principle, we do negative work when we walk but as stated above our muscles spend energy.