Hardest known natural problem in P?
The AKS Primality testing algorithm may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time.  See Primality testing with Gaussian periods (Lenstra and Pomerance).