I understand your point about using an interface with only one implementation to clarify the contract. I can tell you one disadvantage I see: It complicates source code navigation from the client class to the implementation. On the other hand, I don't see any problem on using public and private to define the contract.
If you want to promote a private method to make it "more important", in order to test it and point out a potential new class to emerge, one option I've taken some times is to give the method package access. Although that means to work the opposite way you point, having the tests and the tested code in the same package.
I must say I don't really see big advantages and disadvantages between the two ways of working, though.