Do you know a faster algorithm to color planar graphs?

It sounds to me that you're not claiming that your algorithm is guaranteed to find a 4-coloring of a planar graph, just that it usually does so very quickly.

A standard reference for heuristic algorithms for coloring planar graphs is "Heuristics for Rapidly Four-Coloring Large Planar Graphs," by Craig A. Morgenstern and Henry D. Shapiro, Algorithmica 6 (1991), 869–891. They do use a modification of Kempe chain ideas, but I don't know if it's the same as yours.

You didn't specify which "implementations you found around the internet," so maybe you already know about this, but ColPack is one such package that you might try, if you haven't already. There is a paper on ColPack that describes it in detail.