Addressing the performance aspect: it's cheaper not to have to create an instance of something pointlessly, but the difference is very likely to be completely irrelevant. Focusing on a clear design is much more likely to be important over time.
Utility methods are frequently static, and if all the methods within a class are static it may well be worth making the class final and including a private constructor to prevent instantation. Fundamentally, with utility classes which don't represent any real "thing" it doesn't make logical sense to construct an instance - so prevent it.
On the other hand, this does reduce flexibility: if any of these utility methods contain functionality which you may want to vary polymorphically (e.g. for testing purposes) then consider leaving them as instance methods - and try to extract some meaningful class name to represent the "thing" involved. (For example, a FooConverter makes sense to instantiate - a FooUtil doesn't.)