Creating An Automatic Employee of Relationship At Signup
When someone makes a contribution on behalf of an organization, the relationship is automatically is created. I just tested this on my local sandbox, using the default "On behalf of Organization" profile.

Please replicate the relationship not being created at a CiviCRM demo and update your question, indicating that you were able to reproduce there.