Los métodos constructores siempre deben ir públicos o por default están bien?

Constructores pueden ser public, private, protected o default(no access modifier at all).

Si lo haces private no significa que no se pueda acceder, simplemente significa que nadie fuera de la clase puede accederlo, private puede resultar util también.

P.e. un uso de un constructor private es para clases singleton.

A singleton class is one which limits the number of objects creation to one. Using private constructor we can ensure that no more than one object can be created at a time.

Depende, el modificador de acceso por default en Java es para que solo pueda usar utilizado por ese mismo paquete, si esa es tu intención está bien, si quieres usarlo fuera de ese paquete tendría que ponerlo público.