My password was very complex
Complex for humans or complex for computers? The two are not the same
8 random characters can be brute forced a lot quicker than "thisisareallylongpassword"
Probably
not a case of brute force, though, as sites like eBay employ a lot of smarts to try and detect that kind of thing. As Zirk says, if you've ever browsed via public wifi without a VPN then consider everything you've done liable to snooping, for starters. Same goes for mobile data, really, though that's a bit harder and snooping that is usually the purview of the security services.
Also, do you use the same password anywhere else? If so, stick your email address in here -
https://haveibeenpwned.com/ - and see if it's ever been in a list of leaked account details. My email address (and password associated with that service), for example, has been pwned
at least seven times - Adobe (2013), Dropbox (2012), last.fm (2012), LinkedIn (2016), Modern Business Solutions (2016), Plex (2015) and River City Media (2017).. all through no fault of my own (see earlier answer to ronnyd!), and that's only the breaches that are public knowledge..