The game may be harder without 5*, but that doesn't mean it's unwinnable.
For example, I've been finding my 4* Palla really great (even though I have 2 5* Sword), because Ruby Sword is real nice to use when utilized properly, and Moonblow is a really wonderful skill.
I'd also probably bench my 4* Robin in favor of 2* Felicia from the recruit map later because he dies easily to anything not typeless Felicia OTOH, has a crazy high Res and a nice set of skills that'll work well with my horrible Res team. She'd also theoretically mend my problem with Manaketes due to her Res.
It's about good synergy and composition, really. 5* are not be all end all unless you're a collector or a waifu/husbando person.