Interfaces are not free. Depending on the implementation, and how you use them, it can have significant runtime costs, some compile cost (though usually negligible) and most importantly, code complexity.
When you see a call to an interface, you don't know what the code does concretely, you only know what it is supposed to do. The actual implementation and how it ties to the interface may by in a completely different place. It is one of my biggest source of headaches when debugging code.
Interfaces are useful, the strategy pattern is useful, but overuse is harmful. My idea is to not use an abstraction unless I know I am going to need it. For example, let's say I need to decode video, and I have a hardware decoder and a software decoder. Here, an abstraction make sense, as I know the software decoder will be prohibitively slow one some platforms, and the hardware decoder won't always be supported. But if the optimized version is sufficiently better so that it makes the old version obsolete, just change the code.
And if I don't know if I will need to change strategies later, I just write the first strategy, and if it calls for an interface later, only then I will do the abstraction.