Can iPhone 5s be tracked if restored completely, and iCloud lock is gone?
Yes, it still can be tracked. 

Anyone with the ability to track the IMEI number can find it if it is online, or using the phone services, since the iPhone is always broadcasting  it.

You can check information about (this is not tracking) yours here http://www.imei.info/

To display your IMEI number read this http://support.apple.com/kb/HT4061, or look at the label on the back of the iPhone.

However, even the IMEI number can be changed by someone who knows how to.