(Solid) tip "tinners" are almost always ammonium phosphate with some tin (or tin-lead) bits mixed in. They are moderately aggressive at cleaning oxides off, so shouldn't be used constantly, but only when needed. The best tip tinner is your solder--tips should always be coated with a small amount of solder.
If some of the oxides are just sticking really well, you could try to mildly abrade them on a brass sponge, copper braid, or similar, but you can't be too hard or you will damage the iron plating (good tips are typically copper core, plated with iron, then chromium everywhere but the working area).
Practice good tip care. I use a Hakko iron and tips at work and mine has lasted about a year (moderately light use, maybe 5-6 projects). Put a good amount of solder on the tip when storing it or leaving it idle for any length of time; don't, for instance, wipe it off, put it in the holder, then leave it on over lunch.
Additional guides:
We'll need more info to help you. First, post a picture of the tip itself. It could be damaged and we'll need to see it to be sure. I'll explain later on why that is important.
Next check your iron's manual and see what it say about time required to heat it up. My (also 25 W) says that 1 minute is needed to reach operating temperature. The heat transfer also depends a lot on the condition of the tip. If the tip is bad, then it could take a while for it to melt solder even if the temperature is reached.
Next are the wires. What size of wires are you using? The size of the wires makes a huge impact on the quality of the soldering and 25 W irons can't handle thicker wires (say greater than \$0.75\mbox{ } mm^2\$).
Are you sure that you're soldering them correctly? The description of the process makes me doubt that. You're supposed to first connect wires mechanically (here are some nice pictures) and then heat up the joint until it reaches the high enough temperature to melt the solder. You should connect the iron to the joint in such way that the both wires are in contact with the iron. Don't forget to have a little bit of solder on the tip of the iron when you make first contact. This will cause better heat transfer and in addition to that, once the tiny bit of solder on the tip flows into the joint, the region near the tip if probably hot enough to get the solder wire. In some cases if you keep heating up both solder wire and the joint at the same time, the flux from the solder wire can melt prematurely. The whole process should take only several seconds or the insulation of the wires can melt. If it takes too long, leave the iron for some time to heat up first.
About the comment:I agree that the water probably did it. Here we actually have several factors that work together to kill the iron. First one is the composition of the tip. Most tips are made from copper and better ones will have some fancy alloy at the tip of the tip which is supposed to prevent the working end from oxidizing. As the tip heats up, it becomes more chemically reactive and will tent to oxidize. To prevent the contamination of the working part, we put some solder wire there which will cover the working end of the tip and oxidize instead. So when we put that into water, it is to be expected that the tip will corrode. In addition to that it may react with any impurities in water itself and get even more contaminated. Same goes for the soldering iron itself. As the tip gets more corroded, its thermal resistance increases meaning that we'll have greater temperature difference between the heater and the tip. When connected to the heater, the tip will act as a cooler and when it's contaminated, its performance will decrease. That may cause the heater to overheat and in some cases my damage it. This may even destroy cheaper soldering irons completely.
Next we have the problem with rapid cooling in the water. When the tip heats up it expands and when it cools, it shrinks. In some cases cooling it very quickly can lead to creation of small cracks and small pieces of the tip may actually fall off. I suspect that the films were made by that process. You naturally want to prevent that from happening and that is another reason why you should let the iron cool off unassisted.
When you combine two of that, you get what you got.
Now for the iron itself... Check where exactly the heating element of the iron comes into contact with the tip and how the system works. If that part isn't corroded, then I'd let the iron be and get a new tip. I fear that agitating the corroded part would only make the problem even worse. If the part where the tip comes into contact with the heater is corroded, then you could try cleaning it somehow. It should (hopefully) make the tip's contact with the heater better. If it's really badly corroded, then consider getting a new iron.
Best Answer
These are Spade terminals, for use with Spade Crimps. You should buy a Crimp Tool to crush these. They are both cheap.
You should not solder to these terminals, as the relay will be at risk of damage from the heat of the iron. Also, when the relay wears out it will be more difficult to replace.