@konsumlamm, here's a test program:

{-# language BangPatterns #-}
module Main where
import Data.PQueue.Prio.Min (MinPQueue)
import qualified Data.PQueue.Prio.Min as Q
import Control.Monad.Trans.State.Strict
glump :: MinPQueue Int Int
glump = Q.fromList [(a, a) | a <- [1..2*10^6]]
hoom :: MinPQueue Int Int -> MinPQueue Int Int
hoom = flip evalState 0 . Q.mapMWithKey
  (\x y -> do
     !old <- get
     put (old + 1)
     pure (x + y + old))
main = print $ take 3 $ Q.toAscList (hoom glump)

On my system, this runs in (give or take)

real    0m1.688s
user    0m1.519s
sys     0m0.168s

If I use traverseWithKey instead, it runs in (give or take)

real    0m2.620s
user    0m2.363s
sys     0m0.256s

That seems to me like enough to care about.