Changing iCloud password might be overreacting...
The design of iOS makes it impossible for third-party apps to access iCloud password when they prompt users to type the password, if the device is not jailbroken. Thus the only way a malware could get the password is make a fake pop-up window asking user to login iCould (developer can draw a pop-up window that looks exactly like the iCloud login, but send the password somewhere else). But there is another problem, on a non-jailbroken device, apps other than App Store itself cannot access the iCloud ID, the fake iCloud window must ask user to type the iCloud ID as well, while other legitimate iCloud access requests only ask for the password.
In this sense, unless you have seen some third-party app asking you to provide both iCloud ID and password, it's impossible for the breacher to get hold of your iCloud ID and password at the same time.