Hi @ssvk ,
I tried this on 2 different organizations, both set with Office 365 E3, Plain Dataverse for Teams (none are upgraded to Full Dataverse)
Power Apps , under "Build" tab, click "See all", select all objects I want to export. (created some example tables and added relationships) . Clicked "Export"

Selected "export all dependencies"

moved to a new trial environment, same specs. plain dataverse for teams. Import seems to work fine

dependencies (relationships) were correctly transferred.
Did you try anything different?
May be some environment issue. Tried to break but couldn't get a failure. Did you get anything like export error message?