Yes, proxy servers are legal. What matters is what you do while connected to that proxy and in which jurisdictions. Some countries don’t allow using proxy servers or VPNs to bypass content restrictions placed in that very country.