That doesn't sound normal to me, but how exactly are you doing the walking? What operating system are you using, is it 32- or 64-bit, which library version, how did you build it, are you using external (ptrace) or in-process (UNW_LOCAL_ONLY) walking, what exact API are you calling to walk, what language and compiler did you use for your program, etc.?
Here are some reference numbers from another profiling tool (igprof) using libunwind a few years back:
The time in clock cycles to walk on average 30-ish stack frames, for very frequent walks (3M/sec) was in the ballpark of 2500, and 70000 for less frequent setitimer interrupts at 200/sec (~5 ms interrupt).